問題リンク
問題概要
正整数\(K,N\)が与えられる。
1以上\(K\)以下の自然数からなる数列\(A_1,...,A_N\)は\(K^N\)通りあるが、それらに対し
\(gcd(A_1,...,A_N)\)の総和を求めよ。
解法
自分は約数包除を使った。
\(f(d)\)を1以上\(K\)以下の自然数からなるgcdが\(d\)の数列の個数とすると、求める答えは
\( \sum_{d=1}^{K}d \times f(d)\)で表される。
ここで\(K\)以下の\(d\)の倍数のみからなる数列全体を考えると
\({\lfloor \frac{K}{d} \rfloor }^N = \sum_{t=1}^{K/d} f(dt)\)
が成り立つ。
よってメビウス変換によりメビウス関数(\(\mu(t)\)を使って
\(f(d) = \sum_{t=1}^{K/d} {\lfloor \frac{K}{dt} \rfloor }^N \mu(t)\)
この式から\(f(d)\)を小さい\(d\)から順に求めた後に和を求めればよい。
計算量は\(O(KlogK)\)になる。
提出
https://atcoder.jp/contests/abc162/submissions/11832281
感想
難しく考えすぎたかも…
