无序对的$gcd$

\(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];

总时间复杂度：\(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];

总时间复杂度：\(O(NlogN)\)

两方法对比

方法二时间复杂度更低，方法一能适用更多额外限制。

例题

Counting Rhyme
Small GCD

热门相关：墨先生，乖乖娶我   傲娇总裁：蜜宠小甜妻！   百炼成仙   小嫂子   邻家三个女人的味道