làm bằng c++ nha các bạn ơi

Ý tưởng

- Có lẽ bạn đã biết để tìm số số 0 ở cuối của một giai thừa thì sẽ có công thức là floor(n/5) + floor(n/25) + floor(n/125) + ...

- Và từ đó chúng ta nhận ra rằng giá trị lớn nhất mà giai thừa chứa k số 0 ở cuối là gần với 5*k

VD: N lớn nhất mà N! có 6 chữ số 0 là 29 (Gần với 5*6 là 30)

- Vậy ta chỉ cần viết một hàm đếm chữ số 0 cuối cùng của một số nguyên dương và lặp từ 0 đến 5*k rồi lấy số nhỏ nhất thỏa mãn điều kiện

- Nhưng nếu triển khai thuật đó thì sẽ có độ phức tạp là O(5k) nên với giới hạn đến 10^15 thì gần như không khả thi

- Chính vì vậy, ta không áp dụng được cách lặp tuyến tính này mà phải áp dụng tìm kiếm nhị phân (Rất khả thi vì đoạn cần tìm kiếm đã sắp xếp tăng dần ngay từ đầu còn tìm kiếm nhị phân thì bạn search mạng nha).

Code

#include<bits/stdc++.h>
using namespace std;
bool check(int p, int n){
    int temp = p, count = 0, f = 5;
    while (f <= temp){
        count += temp/f;
        f = f*5;
    }
    return (count >= n);
}
int findNum(int n){
    if (n==1) return 5;
    int low = 0;
    int high = 5*n;
    while (low <high){
        int mid = (low + high) >> 1;
        if (check(mid, n)) high = mid;
        else low = mid+1;
    }
    return low;
}
int main(){
    long long int n;
    cin >> n;
    cout << findNum(n);
    return 0;
}