无序对的GCD
求\(\sum_{i = 1}^n \sum_{j = i+1}^n GCD(a_i, a_j)\)
\(N\)为上确界，\(n\)为\(a\)数组元素个数，\(D\)为约数个数。
方法一
\(1.\)求出\(d\)，\(d[i]\)表示\(i\)的所有约数（有序）。
时间复杂度：\(O(NlogN)\)
vector<int> d[N + 1];
for (int i = 1; i <= N; i++)
for (int j = i; j <= N; j += i)
d[j].pb(i);
\(2.\)求出\(f\)，\(f[i]\)表示满足\(gcd=ki\)的无序对的数量，\(k\in\mathbb{N^+}\)。
在遍历到第\(j\)个数时，\(cnt[i]\)表示前\(j-1\)个数含有约数\(i\)的个数。
时间复杂度：\(O(nD)\)
vector<i64> f(N + 1);
vector<int> cnt(N + 1);
for (int j = 1; j <= n; j++)
for (auto i : d[a[j]])
f[i] += cnt[i]++;
\(3.\)容斥定理更新\(f\)，此时\(f[i]\)表示满足\(gcd=i\)的无序对的数量。
时间复杂度：\(O(NlogN)\)
for (int i = N; i; i--)
for (int j = 2 * i; j <= N; j += i)
f[i] -= f[j];
\(4.\)求\(ans\)，\(ans\)即表示\(\sum_{i = 1}^n \sum_{j = i+1}^n GCD(a_i, a_j)\)。
ans显然也可由\(\sum_{i = 1}^N f[i]\)表示，求和即可。
时间复杂度：\(O(N)\)
i64 ans = accumulate(f + 1, f + N + 1, 0LL);
总时间复杂度：\(O(NlogN+nD)\)
方法二
\(1.\)求出\(f\)，\(f[i]\)表示满足\(gcd=ki\)的无序对的数量，\(k\in\mathbb{N^+}\)。
时间复杂度：\(O(NlogN)\)
vector<i64> f(N + 1);
for (int i = 1; i <= n; i++) f[a[i]]++;
for (int i = 1; i <= N; i++)
for (int j = 2 * i; j <= N; j += i)
f[i] += f[j];
\(2.\)容斥定理更新\(f\)，此时\(f[i]\)表示满足\(gcd=i\)的无序对的数量。
时间复杂度：\(O(NlogN)\)
for (int i = N; i; i--)
for (int j = 2 * i; j <= N; j += i)
f[i] -= f[j];
\(3.\)求\(ans\)，\(ans\)即表示\(\sum_{i = 1}^n \sum_{j = i+1}^n GCD(a_i, a_j)\)。
ans显然也可由\(\sum_{i = 1}^N f[i]\)表示，求和即可。
时间复杂度：\(O(N)\)
i64 ans = accumulate(f + 1, f + N + 1, 0LL);
总时间复杂度：\(O(NlogN)\)
两方法对比
方法二时间复杂度更低，方法一能适用更多额外限制。