无序对的$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

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