CF1986G2 Permutation Problem (Hard Version)

LuoGu: CF1986G2 Permutation Problem (Hard Version)

CF: G2. Permutation Problem (Hard Version)

将 $\frac {p _ i} i$ 约分得到 $\frac {a _ i} {b _ i}$ ，那么 $[ij | p _ i p _ j] = [b _ i b _ j | a _ i a _ j] = [b _ i | a _ j \wedge b _ j | a _ i]$ ，考虑枚举 $b _ i$ ，找出相同 $b _ i$ 的所有 $a _ i$ ，统计它们的约数，放进一个桶里面，这一部分每一个数只出现一次，复杂度为 $O(n \ln n)$ ；再枚举 $b _ i$ 的倍数 $a _ j$ ，结合上面的桶统计答案，这一部分每一个数在 $b _ i$ 为其约数时出现一次，复杂度为 $O(n \ln n)$ 。

总的思路是将 $[ij | p _ i p _ j]$ 拆开统计实现复杂度的降低。

查看代码

#include <cstdio>
#include <iostream>
#include <vector>
#define pb push_back
using namespace std;
typedef long long L;
typedef vector <int> VI;
const int N = 5e5 + 10;
int n, w[N], v[N], cnt[N];
VI f[N], x[N], y[N];
int gcd (int a, int b)
{
    return a ? gcd(b % a, a) : b;
    }
void init ()
{
    for (int i = 1; i < N; ++i)
        for (int j = 1; i * j < N; ++j)
            f[i * j].pb(i);
}
int main ()
{
    init();
    int T; cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; ++i)
        {
            cin >> w[i], v[i] = i;
            int d = gcd(w[i], v[i]);
            w[i] /= d, v[i] /= d;
        }
        for (int i = 1; i <= n; ++i)
            x[i].clear(), y[i].clear();
        for (int i = 1; i <= n; ++i)
            x[w[i]].pb(i), y[v[i]].pb(i);
        L res = 0;
        for (int i = 1; i <= n; ++i)
        {
            for (int t : y[i])
                for (int s : f[w[t]])
                    ++cnt[s];
            for (int j = 1; i * j <= n; ++j)
                for (int k : x[i * j])
                    res += cnt[v[k]];
            for (int t : y[i])
                for (int s : f[w[t]])
                    --cnt[s];
        }
        for (int i = 1; i <= n; ++i)
            res -= v[i] == 1;
        cout << (res >> 1) << endl;
    }
    return 0;
}