ABC230G GCD Permutation 题解

· · 题解

题目大意

题目传送门

给定一个长为 n 的排列 p，求有多少对 1\le i\le j\le n 满足 \gcd(i,j)\not=1\land \gcd(p_i,p_j)\not=1

## 题目分析 容易得到： $$ \begin{aligned} ans&=\sum_{i=1}^n\sum_{j=i}^n[\gcd(i,j)\not=1\land \gcd(p_i,p_j)\not=1]\\ &=\frac{1}{2}\left(\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)\not=1\land \gcd(p_i,p_j)\not=1]+\sum_{i=1}^n[\gcd(i,i)\not=1\land \gcd(p_i,p_i)\not=1]\right) \end{aligned} $$ 于是现在的答案转变为求出 $$ res=\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)\not=1\land \gcd(p_i,p_j)\not=1] $$ 记 $$ \begin{aligned} A&=\{(i,j)|[gcd(i,j)\not=1]\}\\ B&=\{(i,j)|[gcd(p_i,p_j)\not=1]\}\\ \end{aligned} $$ 那么有 $$ res=\left|A\cap B\right|=\left|U\right|-\left|\overline{A}\right|-\left|\overline{B}\right|+\left|\overline{A}\cap\overline{B}\right| $$ $\left|U\right|$ 是显然的。于是只需求出 $\left|\overline{A}\right|,\left|\overline{B}\right|,\left|\overline{A}\cap\overline{B}\right|$。 ### $\left|\overline{A}\right| \begin{aligned} \left|\overline{A}\right|&=\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1]\\ &=\sum_{i=1}^n\sum_{j=1}^n\sum_{d|i,d|j}\mu(d)\\ &=\sum_{d=1}^n\mu(d)\left(\sum_{i=1}^n[d|i]\right)^2\\ &=\sum_{d=1}^n\mu(d)\left(\lfloor\frac{n}{d}\rfloor\right)^2 \end{aligned}

\left|\overline{B}\right|

先设 f(d)=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(p_{id},p_{jd})=1]，具体怎么求下文再讲。

那么有 \left|\overline{B}\right|=f(1)。

\left|\overline{A}\cap\overline{B}\right|

\begin{aligned} \left|\overline{A}\cap\overline{B}\right|&=\sum_{i=1}^n\sum_{j=1}^n[\gcd(i,j)=1\land\gcd(p_i,p_j)=1]\\ &=\sum_{i=1}^n\sum_{j=1}^n[gcd(p_i,p_j)=1]\sum_{d|i,d|j}\mu(d)\\ &=\sum_{d=1}^n\mu(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(p_{id},p_{jd})=1]\\ &=\sum_{d=1}^n\mu(d)f(d) \end{aligned}

f(d)

\begin{aligned} f(d)&=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}[\gcd(p_{id},p_{jd})=1]\\ &=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{t|p_{id},t|p_{jd}}\mu(t)\\ &=\sum_{t=1}^n\mu(t)\left(\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[d|p_{id}]\right)^2 \end{aligned}

由于 id 的总数是 O(n\ln n) 的，所以可以想到暴力枚举每一个 id。那么此时只会对 p_{id} 的因数产生贡献。

若记 buc_t=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}[d|p_{id}]，那么贡献就会从 \mu(t)buc_t^2 变成 \mu(t)(buc_t+1)^2。拆开后可以得到贡献增加了 \mu(t)(2buc_t+1)。

预处理出因数就可以动态维护答案了。时间复杂度 O(n\log n\max_{i=1}^nd(i))。

代码

主要代码如下：

signed main()
{
    SetIO();
    cin >> n;
    Init(n);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j += i)
            factor[j].eb(i);
    for (int d = 1; d <= n; d++)
    {
        for (int i = d; i <= n; i += d)
            for (int t : factor[a[i]])
            {
                f[d] += mu[t] * (2 * buc[t] + 1);
                buc[t]++;
            }
        for (int i = d; i <= n; i += d)
            for (int t : factor[a[i]])
                buc[t]--;
    }
    ans = 1ll * n * n;
    for (int d = 1; d <= n; d++)
        ans -= mu[d] * (n / d) * (n / d);
    ans -= f[1];
    for (int d = 1; d <= n; d++)
        ans += f[d] * mu[d];
    for (int i = 2; i <= n; i++)if (a[i] != 1)
        ans++;
    cout << ans / 2;
    return 0;
}