[题解] AT_abc230_g [ABC230G] GCD Permutation

Monke_FClBrI · 2025-02-27 22:33:20 · 题解

大家好，我不会莫反，我是暴力老哥。

考虑给定序列 a 求 \gcd(a_i,a_j)\ne 1 的 (i,j) 数量，这是容易做的。我们先对于每个值统计出 \gcd(a_i,a_j) 是其倍数的数量，然后枚举倍数容斥一下即可。

我们考虑本题就相当于做两次上面的东西套起来：先枚举一个值 x，并计算 x|\gcd(i,j) 的数量，然后容斥。计算这个就是将每个满足 x|i 的 p_i 提出来做上面的东西。

但是直接做跑得很慢。考虑对每个 x 计算的过程。我们先用一个数组 d 记录所有 x|i 的 p_i 的因数 y 并统计每个因数出现次数，之后将 d 排序，从大到小计算对数，然后枚举 y 的倍数并减去倍数的方案数。

我们发现枚举倍数的这部分有两种方法：直接枚举 y 的倍数，或者枚举在 d 中比 y 索引大的位置，并选取其中的倍数。当然两种都无法直接通过。但两者各有优劣，第一种对于较大的 y 运算量很小，而 y 较小时很慢，但第二种中可取的范围总是比较有限。所以考虑每次枚举倍数时选择两种中运算量小的一种。

不会算复杂度，但是没怎么卡常就过了，时间 3.9\text s。第二种方法中取模比较慢，调一下参可能更快。

代码

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define SZ(x) (int)(x).size()
using namespace std;
const int N=2e5+5;
int n,a[N],d[N];
ll f[N],g[N],ans;
basic_string<int> ve[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=2;i<=n;i++)
        for(int j=i;j<=n;j+=i)
            ve[j].pb(i);
    for(int i=2;i<=n;i++){
        int t=0;
        for(int j=i;j<=n;j+=i)
            for(int v:ve[a[j]])
                if(!g[v]++)d[++t]=v;
        sort(d+1,d+t+1);
        for(int j=t;j;j--){
            g[d[j]]=g[d[j]]*(g[d[j]]+1)/2;
            if(n/d[j]<t-j)
                for(int k=d[j]*2;k<=n;k+=d[j])
                    g[d[j]]-=g[k];
            else for(int k=j+1;k<=t;k++)
                if(d[k]/d[j]*d[j]==d[k])g[d[j]]-=g[d[k]];
            f[i]+=g[d[j]];
        }
        for(int j=1;j<=t;j++)g[d[j]]=0;
    }
    for(int i=n;i>1;i--){
        for(int j=i*2;j<=n;j+=i)
            f[i]-=f[j];
        ans+=f[i];
    }
    cout<<ans<<'\n';
    return 0;
}

（逃