โปรแกรม C++ หาค่า X ที่น้อยที่สุดที่ทำให้ X! มีศูนย์ท้ายอย่างน้อย Y ตัว

เราต้องรับตัวเลข Y เราจะหาตัวเลข X ที่น้อยที่สุด ซึ่ง X! มีศูนย์ท้าย (trailing zeros) อย่างน้อย Y ตัว ตัวอย่างเช่น ถ้า Y = 2 ค่า X = 10 เพราะ X! = 3228800 มีศูนย์ท้าย Y ตัว

เราสามารถแก้ได้โดยใช้การค้นหาแบบทวิภาค (binary search) จำนวนศูนย์ท้ายใน N! กำหนดโดยจำนวนตัวประกอบ 5 ใน N! สามารถหา X ได้ด้วย binary search ในช่วง [0, 5*Y]

ตัวอย่าง

#include <iostream> 
using namespace std; 

int factorCount(int n, int X) { 
    if (X < n) 
        return 0; 
    return (X / n + factorCount(n, X / n)); 
} 

int findX(int Y) { 
    int left = 0, right = 5 * Y; 
    int N = 0; 
    while (left <= right) { 
        int mid = (right + left) / 2; 
        if (factorCount(5, mid) < Y) { 
            left = mid + 1; 
        } else { 
            N = mid; 
            right = mid - 1; 
        } 
    } 
    return N; 
} 

int main() { 
    int Y = 4; 
    cout << "Smallest value of X: " << findX(Y); 
}

ผลลัพธ์

Smallest value of X: 20