ABC 162 E - Sum of gcd of Tuples (Hard)

問題

$1$ 以上 $k$ 以下の整数からなるすべての長さ $n$ の配列 $A$ の最大公約数の和を求めよ。($n,k\leq 10 ^ 5$)

atcoder.jp

解説

最大公約数が $i$ になるような配列の個数を $F _ i$ として $\displaystyle \sum _ {i = 1} ^ {k} iF_ i $ を計算すればよい。
最大公約数が $i$ になるような配列の個数は全部 $i$ の倍数である配列の個数から全部 $2 i, 3 i , \ldots$ の倍数である配列の個数を引いたものなので、$i$ が大きい方から数える。
全部 $i$ の倍数である配列の個数は $\displaystyle\left[\frac{k}{i}\right] ^ n$ である。

実装

n, k = map(int, input().split())
p = 10**9+7
F = {}
s = 0
for i in range(k, 0, -1):
    F[i] = pow(k//i, n, p)
    for j in range(2*i, k+1, i):
        F[i] -= F[j]
    s = (s + F[i] * i) % p
print(s)

atcoder.jp