ABC162 E - Sum of gcd of Tuples (Hard) - かんプリンの学習記録

問題概要
思考の流れ
提出プログラム
感想

問題概要

${1\le N\le 10^{5}}$ と ${1\le K\le 10^{5}}$ が与えられる. ${1}$ 以上 ${K}$ 以下の整数からなる数列として考えられるもの全てについて, その数列のすべての要素の ${\gcd}$ の総和を ${10^{9}+7}$ で割った余りを求めよ.

思考の流れ

ありうる数列は ${K^{N}}$ 個あるらしいので, 列挙は無理.

${\downarrow}$

そうなると「全列挙できない場合は寄与分を考える」が使えそう.
${1\le X\le K}$ の各 ${X}$ について, ${X}$ が何回足されるかを考える.

${\downarrow}$

${\gcd}$ が ${X}$ になるときってどんなとき？
数列の全要素が ${X}$ で割り切れ, ${2X,3X,\ldots}$ で割り切れないとき.

${\downarrow}$

${X}$ で割り切れるものから ${2X,3X,\ldots}$ のいずれかで割り切れるものを引けばいい.
数列の全要素が ${X}$ で割り切れるような数列の個数は ${\lfloor \frac{K}{X}\rfloor}^N$ 個.
数列の全要素が ${2X,3X,\ldots}$ のいずれかで割り切れる数列の個数は？
(包除原理か？無理...)

${\downarrow}$

ここで, 大きい ${X}$ から順に「数列の全要素が ${X}$ で割り切れ, ${2X,3X,\ldots}$ で割り切れないような数列の数」を求めていくと, ${X}$ を求めたいときに, ${2X,3X,\ldots}$ が既に求まっている(それぞれ重複カウントはない)ので ${\lfloor \frac{K}{X}\rfloor}^N$ から引けば求められそう.
ちなみに, これを求めるには ${O(K^2)}$ かかりそうだが, よくみると調和級数の和になっているので ${O(K\log{K})}$ でいける.