AtCoder Beginner Contest 169 D を Python で
お久しぶりです。タムログです。少しモチベーションが下がってしまってコンテストをさぼっていたのですが，今回から再開して，また解説ブログも書いていきたいと思います。今回はまずAtCoder Beginner Contest 169 D を Python で解説していきます。続いてA~Cも書いていきますので，そちらもまた書いたらご覧ください。
それでは，まずは問題文から。
実行時間制限: 2 sec / メモリ制限: 1024 MB×
配点 : 400 点
問題文
正の整数 N が与えられます。 N に対して、以下の操作を繰り返し行うことを考えます。
- はじめに、以下の条件を全て満たす正の整数 z を選ぶ。
- ある素数 p と正の整数 e を用いて、 z=p^e と表せる
- N が z で割り切れる
- 以前の操作で選んだどの整数とも異なる
- N を、N/z に置き換える
最大で何回操作を行うことができるか求めてください。
制約
- 入力はすべて整数である。
- 1≤N≤10^12
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
24
出力例 1
3
例えば、次のように操作を行うことで、 3 回操作を行うことができます。
- z=2(=2^1) とする。( 操作後、N=12 となる。)
- z=3(=3^1) とする。( 操作後、 N=4 となる。 )
- z=4(=2^2) とする。( 操作後、 N=1 となる。 )
入力例 2
1
出力例 2
0
一度も操作を行うことができません。
入力例 3
64
出力例 3
3
例えば、次のように操作を行うことで、 33 回操作を行うことができます。
- z=2(=2^1) とする。( 操作後、 N=32 となる。)
- z=4(=2^2) とする。( 操作後、 N=8 となる。 )
- z=8(=2^3) とする。( 操作後、 N=1 となる。 )
入力例 4
1000000007
出力例 4
1
例えば、次のように操作を行うことで、 1 回操作を行うことができます。
- z=1000000007(=1000000007^1) とする。( 操作後、 N=1 となる。 )
入力例 5
997764507000
出力例 5
7
解説
問題文を一言で言うと，N を素数の異なるべき乗で何回割れるかというような問題です。これはまず N を素因数分解すると見通しがつきます。とりあえず入力例１の n=24 の場合で考えてみると，
24 = 2^3 + 3^1 と因数分解できます。
こうすることで，今回割れる素数は 2と3 であることが分かります。
では，このときある整数 e を用いて何回 p^e の形を作って N を割れるか，と言うものですが，これは e を１から順番に見ていけばいいです。２４の場合は，例えばまず割りたい素数を２としたときには
- 24 ÷ 2^1 = 12
- 12 ÷ 2^2 = 3
となり，これ以上素数２のべき乗（次は2^3）で割れないから，これで終わりです。
今度は素数３でも同じことをして，１回しか割れないから，結局２４の場合は2+1=3を出力すればいいことになります。
64の場合も同様です。素因数分解すると
64 = 2^6 ですから，これは2だけで割ればよくて，
- 64 ÷ 2^1 = 32
- 32 ÷ 2^2 = 8
- 8 ÷ 2^3 = 1
となり，以上で出力は３です。
実際考えるときは N を割っていきましたが，素因数分解しているのでわざわざ N を割って考える必要はありません。素因数分解するときに出てきた素数のべき乗について，それぞれ
-1, -2, -3 ・・・
と順々に引いていって，０以上になるという条件の下で最大何回引けるか確認します。
例えば 3456 = 2^7 * 3^3 であれば，まず素数２について見ると
- 7 – 1 = 6
- 6 – 2 = 4
- 4 – 3 = 1
- 1 – 4 = -3 ←これはアウト
ですから，3回操作を行えて，素数３の時は
- 3 -1 = 2
- 2 – 2 = 0
- 0 – 3 = -3 ←これはアウト
となり，2回操作を行えて，結局合計５回操作を行えることになります。実際のコーディングの際はこのように操作する回数を計算することになります。
では，コーディングに移ります。素因数分解は
の記事を参考にさせていただきました。このコードによって，例えば２４なら，
factorization(24)
// [[2, 3], [3, 1]]というように素因数分解してくれます。これを用いて，for文を利用し，[i][1]の値を-1,-2,・・・とした結果，0以上になるという条件の下で何回引けるかという値を count に格納していきます。自分のコードでは，a を素因数分解したときの値を入れるリストとし，b を先ほど述べた for 文の中で，-1, -2, ・・・と引いていく数に対応させます。
素因数分解したときに出てくる素数pによって，Nは少なくとも p^1で一回は割れるので，まずそれぞれの素数に対して，count に１を足して，次にp^2，p^3・・・で割れるかというような判断をしています。
注意したいのは N=1 の場合で，この場合に限り1度も割れないので，これだけ別枠で０を出力するようにしています。
それでは解答例に移ります。
解答例
def factorization(n):
arr = []
temp = n
for i in range(2, int(-(-n**0.5//1))+1):
if temp%i==0:
cnt=0
while temp%i==0:
cnt+=1
temp //= i
arr.append([i, cnt])
if temp!=1:
arr.append([temp, 1])
if arr==[]:
arr.append([n, 1])
return arr
n = int(input())
count = 0
a = factorization(n)
if n == 1:
print(0)
exit()
for i in range(len(a)):
a[i][1] -= 1
count += 1
b = 2
while a[i][1] > 0:
a[i][1] -= b
if a[i][1] >= 0:
count += 1
b += 1
print(count)いかがだったでしょうか。久しぶりに解説ブログを上げたのでなかなか書くのが難しいなと思いましたが，もし分からないところや間違っていると思われるところがあれば，気軽にtwitterで教えてください。
それでは！
