Manthan, Codefest 16B a Trivial Problem

Problem - B - Codeforces

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?

階乗の末尾に個ある数は何個あるか．
末尾にが増えるのはなどを通るときである．で，の数より圧倒的に多いのでを通るたびに0が増えると考える．を末尾のの個数とし，

のように5を因数としてもつ分だけ増やす．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  int n;
  cin >> n;

  vector<int> v;
  int cnt = 0;

  rep(i, 5*100000) {
      if(i % 5 == 0) {
          int t = i;
          while(t != 0 &&t % 5 == 0) {
              t /= 5;
              cnt++;
          }
      }

      if(cnt == n) {
          v.push_back(i);
      } else if(cnt > n) {
          break;
      }
  }

  cout << v.size() << endl;
  rep(i, v.size()) {
      cout << v[i];
      if(i == v.size()-1) cout << endl;
      else cout << " ";
  }

  return 0;
}
Feb 29th, 2016
codeforces