ABC162 E - Sum of gcd of Tuples (Hard) (500)
全パターンを愚直に求めると$ O(K^N)で全く間に合わない
gcdの結果がiになる物の数を求める
これはKパターンしか無い
gcdの結果がiになるのは配列の要素が全てiの倍数かつ2i,3i,...の倍数でないものがあること
全てiの倍数になる組み合わせは$ \left(\frac{k}{i}\right)^n通り
これから$ \left(\frac{k}{2i}\right)^n, $ \left(\frac{k}{3i}\right)^n, ...と引いていく
各iについて
n乗を求めるのが$ O(\log N)
2倍、3倍、といった倍数を求めるところが全体で$ (K \log K)
全体で$ K(\log K + \log N)