一、題目
1、題目描述
You task is to find minimal natural number?N, so that?N!?contains exactly?Q?zeroes on the trail in decimal notation. As you know?
N! = 1 * 2 * ... * N. For example, 5! = 120, 120 contains one zero on the trail.
2、輸入輸出
2.1輸入
Input starts with an integer?T (≤ 10000), denoting the number of test cases.
Each case contains an integer?Q (1 ≤ Q ≤ 108)?in a line.
2.2輸出
For each case, print the case number and?N. If no solution is found then print?
impossible.
3、原題鏈接
Trailing Zeroes (III) - LightOJ 1138 - Virtual Judge (vjudge.net)
二、解題報告
1、思路分析
對于一個階乘我們如何計算出它有幾個后綴0呢？
考慮到后綴0只能由2*5貢獻得來，所以我們只需要計算出1~n能夠拆出多少個2/5數對即可
又注意到可拆出的2的數目一定多于5的數目，故而我們求出因子5的數目就是2/5數對的數目
繼而我們可以在O(logn)的時間內計算出n的階乘有多少個后綴0
那么我們只需要二分答案，計算最小的滿足的數字即可
2、復雜度
時間復雜度： O(log^2n)空間復雜度：O(1)
3、代碼詳解
?
#include <iostream>
#include <cstring>
using namespace std;
#define int long long
const int N = 1e7 + 10, mod = 1e9 + 7;
int n, f[N], res = 0;
void solve()
{cin >> n;for (int i = n; i >= 1; i--){f[i] = ((n / i) * (n / i)) % mod;for (int j = i << 1; j <= n; j += i)f[i] = (f[i] - f[j] + mod) % mod;res = (res + f[i] * (i * i) % mod) % mod;}cout << res;
}
signed main()
{ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);//freopen("in.txt", "r", stdin);int _ = 1;while (_--)solve();return 0;
}
