10 約数列挙 Dif:142 ABC180 C：「AtCoder 凡人が『緑』になるための精選50問詳細解説」サンプル

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/9e611a60ba2a49b94e89
次：https://qiita.com/sano192/items/2193fbb57ab66237ed9e

【目標】
・約数列挙のアルゴリズムを理解し、実装できるようになる

【概要】
Nが何で割り切れるか＝Nの約数は何か、つまりNの約数を列挙できれば解ける。約数列挙のアルゴリズムはそこまで難しくないので、内容までしっかり理解して実装できるようになろう。

【方針】
Nの約数がわかればそれを答えて終わり。
問題はNの約数をどのようにして求めるか。

以下の手順でNの約数を確認できる。
・Nが1で割り切れるか確認する。(絶対に割り切れる)
　→1と、N//1を約数として記録。
・Nが2で割り切れるか確認する。割り切れるなら
　→2と、N//2を約数として記録。
・Nが3で割り切れるか確認する。割り切れるなら
　→3と、N//3を約数として記録。
…
・√N<(割る数)になったら終わり。記録した約数を出力する。

例：N=40の場合
・40が1で割り切れるか確認する。
　→1と、40//1=40を約数として記録。
・40が2で割り切れるか確認する。
　→2と、40//2=20を約数として記録。
・40が3で割り切れるか確認する。
　→割り切れない。
・40が4で割り切れるか確認する。
　→4と、40//4=10を約数として記録。
・40が5で割り切れるか確認する。
　→5と、40//2=8を約数として記録。
・40が6で割り切れるか確認する。
　→割り切れない。
・√40=6.32...<7だから終わり。
記録した約数=1,2,4,5,8,10,20,40

なぜ√N<iになったら終わりか？
√Nより大きい数で割り切れてもそのペアはすでに記録されているはず。そのため√Nより大きい数での試し割りは不要。
(√40=6.32...より大きい8は40を割り切れるが、そのペアである5で割った時、40//5＝8も約数として記録されている)

以上の方法を使い、計算量O(√N)で約数が列挙できる。
制約はN<=10^12だから√N<=10^6。これならTLE(実行時間制限超過)しない。

【実装】
まず約数列挙する関数を作ろう。
Nを引数として受け取り、約数を記録したリストを返す関数。
名前はDivisor_Listとする。

def Divisor_List(N):

まず約数を格納するリストを作る。

    divisor=[]

i=1~√Nまで順に割り切れるか確認する。

    i=1
    while i**2<=N:
        if N%i==0:
            divisor.append(i)
            if i!=N//i:
                divisor.append(N//i)
        i+=1

while i<=math.sqrt(N)
と書けばi=1~√Nの範囲とできそうだが、ルートをとるなど少数が出る操作はプログラミングにおいて誤差がでる可能性がある。
そのため
i<=√N
→i^2<=N
と置き換え、少数が出ないようにwhileの範囲を指定している。

Nがiで割り切れるか確認し、割り切れる場合はi、N//iを約数として記録。
if i!=N//i
というのは約数のペアが同じ場合に重複して記録しないため。
例えばN=49に対してi=7を試す場合、
i=7
N//i=7
となり、このif文がないと7を2回divisorに追加してしまう。

最後にdivisorをソートして返す。

    divisor.sort()
    return divisor

この関数の計算量は約数の個数をkとしてO(√N+klogk)となる。klogkの部分はソートを行うため。ただしほとんどの場合klogkは√Nに比べて非常に小さいので気にしなくてよく、実質の計算量はO(√N)と覚えておけば良い。

入力を受け取る。

N=int(input())

ansという変数にNの約数リストを格納する。

ans=Divisor_List(N)

あとはansを順に出力するだけ。

for x in ans:
    print(x)

for x in リスト:
と書くとリストの要素を一つずつxに格納して処理ができる。便利な書き方なのでぜひ他の問題でも使ってほしい。

【コード全文】

def Divisor_List(N):
    divisor=[]

    i=1
    while i**2<=N:
        if N%i==0:
            divisor.append(i)
            if i!=N//i:
                divisor.append(N//i)
        i+=1

    divisor.sort()
    return divisor

N=int(input())

ans=Divisor_List(N)

for x in ans:
    print(x)

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/9e611a60ba2a49b94e89
次：https://qiita.com/sano192/items/2193fbb57ab66237ed9e