Mr. Santa asks all the great programmers of the world to solve a trivial problem. He gives them an integer m and asks for the number of positive integers n, such that the factorial of n ends with exactly m zeroes. Are you among those great programmers who can solve this problem?
The only line of input contains an integer m (1 ≤ m ≤ 100 000) — the required number of trailing zeroes in factorial.
First print k — the number of values of n such that the factorial of n ends with m zeroes. Then print these k integers in increasing order.
1
5
5 6 7 8 9
5
0
The factorial of n is equal to the product of all integers from 1 to n inclusive, that is n! = 1·2·3·...·n.
In the first sample, 5! = 120, 6! = 720, 7! = 5040, 8! = 40320 and 9! = 362880.
题意:统计哪些数阶乘的末尾有m位‘0’ 输出个数 并按照升序输出这些数
题解:数学知识 涨姿势
我们知道阶乘下 产生‘0’位只能是 2*5=10产生‘0’位
那么‘0’位的个数取决于‘2’和‘5’的个数
相比之下‘5’的个数更少 所以末尾‘0’的个数取决于阶乘中‘5’的数
所以可以预处理出所有数含有因数‘5’的个数 也就代码中fun的作用
vector存储为一个数x 对应的x!中5的个数也就是结果。
1 #include<bits/stdc++.h> 2 #define ll __int64 3 #define mod 1e9+7 4 #define PI acos(-1.0) 5 #define bug(x) printf("%%%%%%%%%%%%%",x); 6 #define inf 1e8 7 using namespace std; 8 #define ll __int64 9 int fun( int x) 10 { 11 int flag=0; 12 if(x%5==0) 13 { 14 while(x%5==0) 15 { 16 x/=5; 17 flag++; 18 } 19 } 20 return flag; 21 } 22 vector<int>ve[100005]; 23 int m; 24 int main() 25 { 26 scanf("%d",&m); 27 int gg=0; 28 for(int i=1;i<=500000;i++) 29 { 30 gg+=fun(i); 31 if(gg==m) 32 ve[gg].push_back(i); 33 } 34 printf("%d ",ve[m].size()); 35 if(ve[m].size()) 36 cout<<ve[m][0]; 37 for(int i=1;i<ve[m].size();i++) 38 cout<<" "<<ve[m][i]; 39 cout<<endl; 40 return 0; 41 }