题目链接:https://vjudge.net/problem/LightOJ-1138
Time Limit: 2 second(s) | Memory Limit: 32 MB |
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.
Input
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.
Output
For each case, print the case number and N. If no solution is found then print 'impossible'.
Sample Input |
Output for Sample Input |
3 1 2 5 |
Case 1: 5 Case 2: 10 Case 3: impossible |
题意:
求是否存在一个数n,使得 n! 的十进制表示末尾有Q个0,如存在,输出最小值。
题解:
1. 对 n! 进行质因子分解:n! = 2^a1 * 3^a2 * 5^a3 * …… 。
2.可知质因子2出现的次数大于质因子5出现的次数,且质因子中只有2*5 = 10。综上,有多少个质因子5,末尾就有多少个0。
3.那怎么知道 n! 里面有多少个质因子5呢?
答: 从1到n,有多少个数是5的倍数呢? n/5 个。 当这n/5数格子除以5之后,又还剩几个数是5的倍数呢? 那就是 (n/5)/5 个,然后一直下去。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = 1e6+; LL Count(LL tmp)
{
LL sum = ; //不能定义int
while(tmp) sum += tmp/, tmp /= ;
return sum;
} int main()
{
int T, kase = ;
scanf("%d", &T);
while(T--)
{
LL Q;
scanf("%lld", &Q);
LL l = , r = LNF;
while(l<=r)
{
LL mid = (l+r)/;
if(Count(mid)>=Q)
r = mid - ;
else
l = mid + ;
} printf("Case %d: ", ++kase);
if(Count(l)!=Q)
printf("impossible\n");
else
printf("%lld\n", l);
}
}