Atcoder Problems という競プロを勉強する上でのコンテンツがあります。URL
今回は、hard100問の内、8問目を解説していきたいと思います。
問題名 【E – Double Factorial】
入力
N：数字の大きさ
考察
まずはじめに、N< 10^18なので、Nについてfor文すると、TLEすることがわかります。
すなわち、loop処理をするにしても、事前に何らかの数学的処理を行わないといけないということです。
問題の性質について考える
「末尾に0が何個つくか？」というのは「10の倍数が何回かけられているか？」と読み替えることができます。
もっと言うなら、「それまでに2の倍数と5の倍数の小さい方は何回かけられていますか？」と言えます。（なぜなら、10の倍数は2と5の積で表されるためです）
POINT 問題の性質から問題を言い換えよう
問題の性質について考える2
もう少し問題の性質についてみていきます。
今回、Nが奇数のときは、f(N)も奇数になり、Nが偶数のときはf(N)も偶数になります。
どうやらNの偶奇が答えに関係しそうなので、今回は、偶奇に注目して問題を読み解いていきます。
N が奇数のとき
奇数は奇数×奇数のとき以外奇数にならないので、どのような奇数をとっても約数に偶数を持つことはない。つまり、偶数がかけられることがないので、絶対に10の倍数になることはないです。
Nが偶数のとき
約数に奇数を持つことがあるので、2の倍数と5の倍数の数を数え上げ、その最小値が答えになります。
しかし、5の倍数のほうが少ないのは、自明です。そのため、今回は5が何回かけられたかを数え上げています。
このときのポイントとして、
50 = 5*5*2 や 250 = 5*5*5*2のように一つの数に何度も5がかけられる場合もあるので、それについても数え上げる必要があります。(下に例)
なので、最初は10の倍数の数を数え、その後10*5の倍数,10*5^2の倍数・・・と数えます。これによりNまでの数字の中に5が何回かけられているかがわかります。
ex) 260の場合
5の倍数 = [10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260]
25の倍数 = [50,100,150,200,250]
125の倍数 = [250]
#250は三回出てきている→250は三回5がかけられていると考えることができるとなるので、合計で5の倍数は32個あるとわかります。
コード
import sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def II(): return int(sys.stdin.readline())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def S(): return sys.stdin.readline().rstrip()
readline = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
N = II()
if N%2 ==1:#奇数なら答えは0
print(0)
exit()
#以下偶数なら
a = 10#初期値
cnt = 0
while a <= N:
tmp_cnt = N //a
#Nまでにaをやくすうにもつ数字が何個あるか
cnt += tmp_cnt
a *= 5
# aを5の指数乗に大きくする
print(cnt)まとめ
500点問題になると、数学的理解が必須になってくる気がする・・・
今更、数学の勉強する気はないですが、出てきた問題に対しては真摯に向き合っていきたい
コメント