No.020 D

最初の部分点は最小公倍数を全探索で求めるのだろう.

2番目の部分点は, $i, K$ の最大公約数 $g$ をユークリッドの互除法で求め, 最小公倍数を $LCM(i, K) = iK/g$ で計算し, あとは $i$ を $1$ から $N$ までぶん回すのだろう.

しかし $N$ が大きいのでこの方法では満点は取れない.

まず, $i$ と $K$ が互いに素の場合は, $LCM(i, K) = iK$ である. このようになる $i$ の和 $S$ を求める.

$K$ に含まれる素因数をたとえば $p, q, r$ として, $n$ の倍数の集合を $A_n$ とすると, 包除原理を使って,

$$\begin{align} \sum(A_1) - S &= \sum(A_p \cup A_q \cup A_r) &= \sum(A_p) + \sum(A_q) + \sum(A_r) &\qquad - (\sum(A_p \cap A_q) + \sum(A_q \cap A_r) + \sum(A_r \cap A_p)) &\qquad + \sum(A_p \cap A_q \cap A_r) \end{align}$$

となる. $K$ に含まれる素因数の数は高々 $9$ 個なので十分間に合う.

次に, $\gcd(i, K) = g$ となる $i$ の和を考える. これは $N = N/g, K = K/g$ とすると $i$ と $K$ が互いに素の場合になるので, 同様に計算できる.

以下はすべての $g$ ($K$ の約数) について同様の計算を行う.