くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Beginner Contest 172 D - Sum of Divisors

Python3で解く AtCoder Beginner Contest 172 D - Sum of Divisors

AtCoder 競プロ ABC-D 約数の個数 定数倍

いい感じに約数の個数を数える必要がある。

概要

問題

  • 正整数{\displaystyle N}が与えられる。
  • {\displaystyle X}の約数の個数を{\displaystyle f(X)}とする。
  • {\displaystyle K}を{\displaystyle 1} から{\displaystyle N}まで動かし、{\displaystyle K \times f(K)}の和を求める

解くときに考えた内容

N基準の約数表を考える

{\displaystyle N}の値を{\displaystyle N}の約数分用意すればいいので、こんな感じのテーブルが欲しい。
（実際の約数は必要ないんだけど、個数が分かれば）
このテーブルが得られれば、列名が{\displaystyle N}の値を全て合計すれば目的の計算になる。（{\displaystyle N} * 約数の数 ）

{\displaystyle N} {\displaystyle a}（{\displaystyle N}の約数の候補）
1 1
2 1
2 2
3 1
3 3
4 1
4 2
4 4

だけども、{\displaystyle N}をベースにすると、結局Nのループの中で、約数列挙をするので{\displaystyle O(N^{2})}。工夫しても {\displaystyle O(N\sqrt{N})}なので {\displaystyle 10^7 \times 10^{3.5})}で厳しい。

約数基準の約数表を考える（定数倍の考え方）

これを視点をかえて {\displaystyle a}基準で考えてテーブルを作る。
これは、 {\displaystyle 1}から {\displaystyle N}以内で、約数 {\displaystyle a}はどの{\displaystyle N} のときに約数になるか考えることができる。

{\displaystyle a}（{\displaystyle N}の約数の候補） {\displaystyle N}
1 1
1 2
1 3
1 4
2 2
2 4
3 3
4 4

{\displaystyle N = 10}として、もう少し長く書く

{\displaystyle a}（{\displaystyle N}の約数の候補） {\displaystyle N}
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
2 2
2 4
2 6
2 8
2 10
3 3
3 6
3 9
4 4
4 8
5 5
5 10
6 6
7 7
8 8
9 9
10 10

これも同様に、列名が{\displaystyle N}の値を全て合計すれば目的の計算になる。これを出力するときは、先ほどよりも計算量を少なくできる。
上記の表をみると、{\displaystyle O(N)}以内の{\displaystyle O(a)}の定数倍が表にに存在していることが理解できる。 {\displaystyle a}を{\displaystyle 1}から{\displaystyle N}まで回したときの計算量は {\displaystyle n \times (\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n-2}+ \frac{1}{n-1} + \frac{1}{n})} となり、括弧内は調和級数なので{\displaystyle O(log{N}}であるので、全体では{\displaystyle O(Nlog{N})}

しかし、これをそのままコードにしてもTLEになる。{\displaystyle 10^8}でもアウトなのかもしれない。（これを通すにはさらなる高速化をするためにNumbaやCythonを使うなどする必要があるみたい。これはこれで使い方を理解しておく必要はある。特にNumbaは理解を深めておこう。）

定数倍であることから等差数列の和と考える

で、どうするかというと、 結局{\displaystyle N}の範囲内の定数倍だけなら等差数列の和で考えればいいぢゃん！
{\displaystyle N}の範囲の定数倍の個数は{\displaystyle N} を1から{\displaystyle N}で割り算した時の商であることを利用する。
商を{\displaystyle y}とすると {\displaystyle \frac{(y+1) \times (y)}{2} \times a}

コード

n = int(input())
ans = 0
# 定数倍かつ等差数列の和。これなら通るO(N)
for a in range(1, n+1):
    # yはnまでにおける約数aの候補数
    y = n // a
    ans += (y+1) * y * a // 2
print(ans)

# # 論外パターン O(N**2)
# for N in range(1, n+1):
#     for i in range(1, n+1):
#         if N % i == 0:
#             ans += N
#             i += 1
# print(ans)

# # 定数倍で考える　O(NlogN)
# これ通らないのは辛い。。。
# for a in range(1, n+1):
#     for N in range(a, n+1, a):
#         ans += N
# print(ans)