ABC162 E Sum of gcd of Tuples (Hard)
gcdが
$ k
となる必要条件は,
$ A_i
すべてが
$ i
の倍数であることである. よってまずそのような場合の数を各
$ k
について求める. そして後から
$ 2i, 3i, ...
の値を引いていけばよい.
計算量は
$ O(N log log N)
となる.
実装例:
https://atcoder.jp/contests/abc162/submissions/19200674