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