あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC162 E - Sum of gcd of Tuples (Hard)

競プロ

問題原文

問題要旨

１以上 $K$ 以下の整数からなる長さ $N$ の数列 $A$ を考える。
考えうる数列 $K^{N}$ 通り全てについて、 $gcd(A_1, A_2 ... A_N)$ を計算し、その総和を求めよ。

$2 \leq N \leq 10^{5}$
$1 \leq K \leq 10^{5}$

解法

まともには到底計算できないので、 「gcdが $X$ になるようなものは何通りあるか？」 を考える。
まずgcdが $X$ になるためには、 $A$ は全て $X$ の倍数である必要がある。そして、このようなものは $(\frac{K}{X})^{N}$ 通りある。（切り捨てで）
ただし、この中には gcdが $2X$ , $3X$ ... になるものも含まれているので、それらを引く必要がある。（例えば、 $X=2$ で、 4, 4, 8 とかだとgcdは2でなく4になってしまう）二重ループのように見えるが、よく見るこれは調和級数っぽい形なので大丈夫。

また、gcdが $X$ になるものを計算するためには、gcdが $2X, 3X...$ になるものの計算を終えておく必要があるため、 $X$ は大きい方から計算する。

実装

N, K = map(int, input().split())
MOD = 10 ** 9 + 7

# dp[i] := gcdがiになるようなものの通り数
dp = [0] * (K + 1)
for k in reversed(range(1, K + 1)):
    cnt = pow(K // k, N, MOD)
    for i in range(2, K + 1):
        if i * k > K:
            break
        cnt -= dp[i * k]
    dp[k] = cnt

ans = 0
for k, cnt in enumerate(dp):
    ans += k * cnt
    ans %= MOD
print(ans % MOD)

感想

本番は「gcdが $X$ になるためには $X$ が最低１つ必要」という最低最悪の勘違いをしてしまった。
結局気付けたのは終了２分前で間に合わなかった。なんか怪しい、何かがおかしいと思ったらとりあえず愚直を書いてサンプルを増やそうね。。。