ABC020 D - LCM Rush - ツバサの備忘録

問題
 提出コード(100点)
提出コード(満点)
100点から満点にもっていくことができず、解説を見ました…
言われれば確かにそうだけど～って感じですね。

解法

まずは100点までです。
$K$ の制約が少ないので、 $K$ について何かをするんだろうな、という気持ちになります。
すると、 $N$ までの数の中を、 $K$ で割った余りによって分類すると、
そのあまりが等しい数については、最大公約数も等しいことがわかります。
ここで、 $x$ と $y$ の最小公倍数 $LCM(x,y)$ は、おなじく $x$ と $y$ の最大公約数を $GCD(x,y)$ と表現したとき、
$\frac{xy}{GCD(x,y)}$
と表すことができます。
ので、 $K$ で割った余りが $x$ となるような数の総和をもとめ、そこに $K/GCD(x,K)$ をかけてあげれば、 $K$ で割った余りが $x$ となるような数と、 $K$ の最小公倍数の総和が求められます。
これを、全ての $x$ に対して行えば、 $O(K)$ でこの問題を解くことができます。
$K$ で割った余りが $x$ となるような数は、
$iK + x$ と表記することができます。
ここで、 $i$ は $0$ 以上 $(n-x)/K$ (切り捨て)以下の数となります。
$p = (n-x)/K$ とおくと、
$K$ で割った余りが $x$ となるような数の総和は、次のような計算式で求められます。
$px + \frac{Kp(p+1)}{2}$
ということで、
$(px + \frac{Kp(p+1)}{2}) 　\times \frac{K}{GCD(x,K)}$
を $1~K$ の $x$ に対して行えば、答えを求めることができます。 $10^{9}+7$ で余りをとるタイミングや、割り算のタイミングに気を付けましょう。
ということで、ここまでは今回自分が自力でできた部分です。
ここから先は、素因数分解やらなんやらをするのかなぁと思っていたのですが…
解法自体は解説そのままです。
結局、 $GCD(i,K)$ のパターンは、 $K$ の約数にしかならないので、 $1$ ~ $N$ の $x$ について、 $GCD(x,K)$ のパターンによって分けて総和を求め、あとは上と同じようにその総和と $\frac{K}{GCD(K,x)}$ の積を求めていけば答えが求まる、というものです。
そのために、まずは $GCD(K,x) = g$ となるような $x$ の総和を求める方法を考えてみます。
これは、 $GCD(K/g,x/g) = 1$ となるような $x/g$ の総和を求め、最後に $g$ 倍したものと同じになります。この総和は、包除原理を用いると、うまく計算することができます。
$K/g$ を素因数分解し、素因数の種類を洗い出します。今回は、例として3種類の素因数が存在し、 $a^2 b^3 c^4 = K/g$ だったとします。
このとき、まずは $1$ ~ $x/g$ についての総和を求め、そこから $GCD(K/g,i) \neq 1$ となるような $i$ を引いていくことを考えます。
そして、この後は

素因数を奇数種類使用した数の倍数の総和を減算し、偶数種類使用した数の倍数の総和を加算する

という操作を行います。
今回の例だと、 $a,b,c$ および $abc$ それぞれについて、 $1$ ~ $x/g$ の中での倍数の総和を求め、減算し、 $ab,bc,ac$ の倍数の総和については加算し直します。また、同じ素因数が2つ以上含まれているような場合( $a^2bc$ など)は、無視します。
総和を求めるときは、上で行ったような総和の求め方と同じようなことをします。
$a$ の倍数は、 $p/a$ 個(切り捨て)存在するので、これを $j$ 個としたときに、
$\frac{aj(j+1)}{2}$
という計算をすれば、総和を求めることができます。
また、素因数の種類および、同じ種類の素因数が2つ以上使用されているかどうかは、よくある素因数分解のアルゴリズムを用いれば、容易に調べることができます。

さて、 $GCD(K/g,x/g) = 1$ となるような $x/g$ の総和を求めることができたので、あとは $g$ 倍すれば $GCD(K,x) = g$ となるような $x$ の総和になります。
あとは、全ての $g$ について同じことを繰り返せば終わりです。 $g$ は、先ほどと同様よくある素因数分解等のアルゴリズムのようなものを使えば、 $O(\sqrt{K})$ で洗い出すことができます。
ということで、これらの式をバグなく気合で組み立て計算すれば、この問題を解くことができます。