じゅぴろ君が「これは中受典型」と言いそうな雰囲気がありますね。
問題概要
以上の整数 が与えられる。
を計算した値において、末尾に何個の 0 がつくのかを求めよ。
制約
考えたこと
これとよく似た形で、たとえば
の末尾に 0 が何個つくか?
という感じの問題は、中学受験でも高校受験でも大学受験でもよく見る問題ではある。具体的な解法も割と明快で、 を
と素因数分解したときに、 個の分だけ「2 と 5 のペアを作って 10 を作る」ことができる。よって、 の末尾には 個の 0 がつくことになる。
そして、割と明らかに となっていることがわかる。よって を求めればよい。 を求めるには、以下のように考えればよい。
- のうち、5 で 1 回以上割れる数は、 の 1333 / 5 = 266 個
- のうち、5 で 2 回以上割れる数は、 の 1333 / 25 = 53 個
- のうち、5 で 3 回以上割れる数は、 の 1333 / 125 = 10 個
- のうち、5 で 4 回以上割れる数は、 の 1333 / 625 = 2 個
これらを合計して、266 + 53 + 10 + 2 = 331 個となる。
より具体的に
より具体的には、 が 5 で割れる回数 は、
long long b = 0; while (N) { b += N / 5; N /= 5; }
という感じで求めることができる。
今回の問題の場合
今回の問題は、 ではなく、
なので、微妙に違う。でも実はほとんど一緒。
N が奇数のとき
たとえば のとき、
となる。ここに偶数はない。2 で割れる数がないと、どんなに 5 が大量に供給されたとしても 10 を作ることができない。よって、ダメ。0 個。
N が偶数のとき
たとえば のとき
となる。つまり、結局、 の末尾に 10 が何個あるかを求める問題に帰着された。
まとめ
- が奇数のとき、0 個
- が偶数のとき、 が何回 5 で割り切れるか
計算量は
#include <iostream> using namespace std; long long solve(long long N) { if (N % 2 == 1) return 0; long long res = 0; N /= 2; while (N) { res += N / 5; N /= 5; } return res; } int main() { long long N; cin >> N; cout << solve(N) << endl; }