ABC162 E - Sum of gcd of Tuples (Hard)

問題：E - Sum of gcd of Tuples (Hard)

解答：Submission #11906400 - AtCoder Beginner Contest 162

解法：gcdが等しくなる(a1, a2, ..., an)ごとに計算する。gcdがdの倍数の場合は考えやすく、#{(a1, ..., an) | gcd(a1, ..., an) = x * d (x ≧ 1)} = (k / d)ⁿである。これをどのように gcd(a1, ..., an) = d (x = 1)のケースに限定するかを考える。

N(y) = #{(a1, ..., an) | gcd(a1, ..., an) = y}と表記する。このときN(d) + N(2 * d) + N(3 * d) + ... = (k / d) ^ nであり、N(y)はN(y) = 0 (y > K) であるため、Nを後ろから算出することで、N(y)を全て求めることができる。すなわち、十分大きなxではN(x * d) = 0であり、そこからN((x - 1) * d), N((x - 2) * d), ... と順番に計算してゆけばよい。