題干：

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?

Input

The only line of input contains an integer?m?(1?≤?m?≤?100?000)?— the required number of trailing zeroes in factorial.

Output

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.

Examples

Input

1

Output

5 5 6 7 8 9

Input

5

Output

0

Note

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.

解題報告：

? ? ?直接暴力。

AC代碼1：（二分）（31ms）

#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x,y) memset(x,y,sizeof(x)) #define MC(x,y) memcpy(x,y,sizeof(x)) #define MP(x,y) make_pair(x,y) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; } const int N = 0, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f; int n; int main() {while (~scanf("%d", &n)){int l = 0;int r = 1e9;while (l < r){int m = (l + r + 1) >> 1;int five = 0;int tmp = m;while (tmp) { tmp /= 5; five += tmp; }if (five > n)r = m - 1;else l = m;}int R = l;l = 0;r = 1e9;while (l < r){int m = (l + r) >> 1;int five = 0;int tmp = m;while (tmp) { tmp /= 5; five += tmp; }if (five < n)l = m + 1;else r = m;}int L = l;printf("%d\n", R - L + 1);for (int i = L; i <= R; ++i)printf("%d ", i);puts("");}return 0; } /* 【題意】 給你一個數(shù)組n（1<=n<=1e5） 讓你輸出有多少數(shù)的階乘后恰好有n個0，并依次輸出。 【類型】 二分or暴力 【分析】 肯定滿足，數(shù)字越大，其后的0的個數(shù)也就越多。 于是我們可以二分出最小的l，使得fac[l]>=n 同時我們二分出最大的r，使得fac[r]<=n 然后答案就是區(qū)間段[l,r] 而算fac[l]有多少個0，就是查看fac[l]中有多少個5 因為n不大，所以另外一種做法是暴力。 我們直接求出fac[i]的末尾有多少個0即可 【時間復(fù)雜度&&優(yōu)化】 O(log(n)log(n)) or O(nlogn) */

?

AC代碼2：（枚舉暴力網(wǎng)絡(luò)版）（93ms）

#include<stdio.h> #include<iostream> #include<string.h> #include<string> #include<ctype.h> #include<math.h> #include<set> #include<map> #include<vector> #include<queue> #include<bitset> #include<algorithm> #include<time.h> using namespace std; void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); } #define MS(x,y) memset(x,y,sizeof(x)) #define MC(x,y) memcpy(x,y,sizeof(x)) #define MP(x,y) make_pair(x,y) #define ls o<<1 #define rs o<<1|1 typedef long long LL; typedef unsigned long long UL; typedef unsigned int UI; template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; } template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; } const int N = 0, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f; int n; void solve() {int l = -1;int r = -2;int zero = 0;for (int i = 0; ; ++i){for (int x = i; x && x % 5 == 0; x /= 5)++zero;if (zero == n){if (l == -1)l = i;r = i;}else if (zero > n)break;}printf("%d\n", r - l + 1);for (int i = l; i <= r; ++i)printf("%d ", i);puts(""); } int main() {while (~scanf("%d", &n)){solve();}return 0; }

?

?

AC代碼3：（枚舉自己a）

#include<bits/stdc++.h>using namespace std;int main() {long long tmp,n,m,sum=0;long long l = -1,r = -1;int flag = 0;cin>>m; // tmp = m;for(int i = 1; i<=1000000; i++) {tmp = i;sum = 0;while(tmp!=0) {sum +=tmp/5;tmp/=5;}if(sum == m && l == -1) l = i,r = i,flag = 1;if(sum == m && flag == 1) r= i;if(sum>m && l == -1) {printf("0\n");return 0 ;}}printf("%d\n",r-l+1);for(int i = l; i<=r; i++) {printf("%d ",i);}return 0 ; }

?

總結(jié)：

? ?1.一些小變量的使用要注意啊！別用錯了。

? ?2.注意二分的使用！這種題型也可以！

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的*【CF#633B】 A Trivial Problem（二分或枚举）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。