Trailing Zeroes (III) 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 ≤ 10⁸) 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

Case 1: 5

Case 2: 10

Case 3: impossible

题意：求出现一个最小的数的阶乘满足末尾有连续q个0。

思路：一个最小的数末尾要出现0一定要是能被5或10整除的，0的连续长度与数组大小正相关，故二分数字得解。

 1 #include<set>
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #include<string>
 8 #include
 9 #include
10 #include
11 #include
12 #define mem(a,b) memset(a,b,sizeof(a))
13 using namespace std;
14 const int INF=1e9;
15 typedef unsigned long long ll;
16 typedef long long LL;
17 int main()
18 {
19     int T,cases=1;
20     scanf("%d",&T);
21     while(T--)
22     {
23         int q;
24         LL ans=-1;
25         scanf("%d",&q);
26         int l=1,r=q*5,mid;//为什么右端点是q*5，因为q*5>=ans.想一想为什么（hint：刚才那个序列。。。）
27         while(l<=r)
28         {
29             mid=(l+r)/2;
30             int m=mid,wu=5,count=0;
31             while(m>=wu)
32             {
33                 int p=m;
34                 p/=wu;
35                 count+=p;
36                 wu*=5;
37             }
38             if(count==q)
39             {
40                 ans=mid;
41                 break;
42             }
43             else if(count>q)
44                 r=mid-1;
45             else
46                 l=mid+1;
47         }
48         if(ans==-1)
49             printf("Case %d: impossible\n",cases++);
50         else
51             printf("Case %d: %lld\n",cases++,ans/5*5);
52     }
53 }

代码转自(https://blog.csdn.net/duan_1998/article/details/72566106)

数学二分

Trailing Zeroes (III) LightOJ - 1138 二分+找规律

Input

Output

Sample Input

Output for Sample Input

相关

牛客练习赛91（并查集+二维偏序+二分）

数据结构与算法之PHP查找算法（二分查找）

二分查找模板（准确找定值）

浅谈二分的边界问题

Liquidity Providers 的数学原理

『笔记』组合数学

组合数学练习

算法之二分法

The 2021 CCPC Guilin Onsite【A,I,G(二分),D（思维+构造）,E（最短路】

【YBTOJ高效进阶 21190】欧拉函数（数学）

北京市第14届大学生数学竞赛本科甲乙组试题及参考解答北京市第14届大学生数学竞赛本

洛谷 P3711 - 仓鼠的数学题（多项式）

标签