LightOJ1138 —— 阶乘末尾0、质因子分解

时间:2021-01-17 18:42:07

题目链接:https://vjudge.net/problem/LightOJ-1138

1138 - Trailing Zeroes (III)
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);
}
}