yukicoder No.811 約数の個数の最大化

yukicoder contest 210 に参加した。
A、Bしか解けなかった。
Cは面白い問題だと思ったけど、解けなかった。
というわけで、C の問題はこれ。
No.811 約数の個数の最大化 - yukicoder
解答を見て、なるほどってなったので解説を書く。

解説

ポイントは、自然数 以下の自然数全ての約数と素因数の個数を求めるのは、高々 でできるってこと。
エラトステネスの篩の要領でやればうまくいく。
言われると書けるけど、思いつかない。
簡単に解説。
まず、 以下の自然数を格納したリスト を用意する。
これを前から見ていきながら次の操作をする。
ところで、先に 2.1 を見ると方がわかりやすい。
各 に対して、
1. が であれば、これは合成数である。

が合成数であるとは、 より小さい素数の積で表される、つまり、
より小さい素数たちで割り切れる、ということである。

2. が でなければ、これは素数である。
が素数とは、より小さい素数で割り切れない、ということである。
2.1. 素数 の倍数 を で割れるだけ割る。
すると、 がいくつの を素因数に持つかがわかる。
解答中だと、 がそれにあたる。
更に、これを用いれば、約数の個数も分かる。

あとは、各 以下の自然数 との最大公約数を見て、
その素因数の個数が 個以上か見て、その後、約数の個数を見れば良い。

解答

N, K = map( int, input().split())
Ints = [ i for i in range(N)] #エラトステネられる数列
Primefactors = [0]*N #素因数の個数を格納する部分。
Factors = [1]*N #約数の個数を格納する部分。
for i in range(2, N):
    if Ints[i] == 1:
        continue
    for j in range(1, N):
        if i*j < N:
            t = 1
            while Ints[i*j]%i == 0:
                Ints[i*j] //= i
                Primefactors[i*j] += 1
                t += 1
            Factors[i*j] *= t
        else:
            break
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return(a)
ans = 1
nowfactors = 1
for i in range(2,N):
    if Primefactors[gcd(i,N)] >= K:
        if Factors[i] > nowfactors:
            ans = i
            nowfactors = Factors[i]
print( ans)

おまけ

計算量の話。

    for j in range(1, N):
        if i*j < N:
            t = 1
            while Ints[i*j]%i == 0:
                ...

のところの計算量。
を十分大きな整数とする。
を素数とする。(別に、素数じゃなくても良い)
以下の数で で割り切れるものは、だいたい 個。
以下の数で で割り切れるものは、だいたい 個。
・・・・・・・・
というわけで、
ここの計算量は、

くらい。
自然数の逆数の和のオーダーは 。
今回は素数のみでこの操作を行うことを考えれば、もう少し小さくて、
になる。
Primefactors と Factors を求める計算量は、 になる。