二分+质因数分解，LightOJ 1138Trailing Zeroes (III)

一、题目

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;
}