masuTomo’s blog

競技プログラミングの勉強メモです.主にPythonを使用します.数学の記事も書くかもしれません.

マスター・オブ・整数で競技プログラミング その2

2 素因数分解の利用 素因数の個数

2で割り切れる回数

自然数Nに対して,1~Nまでの自然数の積をPとする。

  • (1)Pが2で何回割り切れるか。

愚直な実装をすれば,素直に2で割り続ければよい。

def func(n):
    if n == 1:
        return 1
    return n*func(n-1)

N = int(input())
P = func(N)
cnt = 0
while P >= 1:
    if P % 2 == 0:
        P //= 2
        cnt += 1
    else:
        break
print(cnt)

ちなみに,

N = 100
P = func(N)
print(P)

--->P = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

であり,N=100程度でもP=N!はけっこう大きい数(158桁)である。

また,N!は再帰関数を用いなくても単純にループ処理でよい。

P = 1
for i in range(1,N+1):
    P *= i

しかし,愚直に割り算を繰り返す方法だと2で割り切れる回数だけ計算を行うことになり,効率が悪い。「2で1回割り切れる」=「素因数として2を1つ含む」と考える。すると「2でn回割り切れる」=「素因数として2をn個含む」となることがわかる。つまり,P=N!について素因数2の個数を調べればよい。 たとえば,N=100として考える。1から100までのそれぞれの自然数に含まれる素因数2の個数と,1から100までの自然数の積に含まれる素因数2の個数は等しいので(これ重要),1から100それぞれの数について素因数2の個数を数えてそれを合計すればよい。明らかにすべての偶数(2,4,8,10,,,,,48,50)は素因数2を含んでいるので,50個は素因数2が含まれていることがわかる。この50個という数は,100÷2=50として求められる。

しかし,4や8はそれぞれ2の2乗,2の3乗なので,4は素因数2を2個,8は3個含んでいるため,このような数について考慮する必要がある。したがって,100÷(2の2乗)=25であることから,素因数2を2個含む数は100までに25個あることがわかる。同様に素因数2を3個含む数は100÷(2の3乗)= 12 あまり4なので,12個。このように考えていくと  100 \div 2 = 50 \\ 100 \div 4 = 25 \\ 100 \div 8 = 12 \cdots 4 \\
100 \div 16 = 6 \cdots 4 \\ 100 \div 32 = 3 \cdots 4
100 \div 64 = 1 \cdots 1\\
したがって素因数2の個数は50+25+12+6+3+1=97(個)

と求めることができる。

N = int(input())
ans = 0
i = 1
while N//(2**i) >= 1:
    ans += N //(2**i)
    i += 1
print(ans)
  • (2)また,Pの末尾に(10進法で)0がいくつ続けて並ぶか。 これは(1)の応用である。末尾に0が来るということは10で割り切れるということであり,それは素因数として2と5を1つ含んでいるということである。したがって,(1)と同様に素因数5の個数を数えて min(素因数2の個数,素因数5の個数)が答えである。さらに minをとらなくても,そもそも素因数2の個数と素因数5の個数では素因数5の個数の方が少ないのは明らかなので,最初から素因数5の個数を答えとしてしまってよい。
#2**iを5**iに変更しただけ

N = int(input())
ans = 0
i = 1
while N//(5**i) >= 1:
    ans += N //(5**i)
    i += 1
print(ans)