AtCoder-abc230_g GCD Permutation 容斥

J - GCD Permutation

传送门： J - GCD Permutation

知识点：素数筛、容斥定理、gcd

题意：长度为n的一个排列a中，求满足\(gcd(i,j)!=1 且 gcd(a_i,a_j)!=1\)的i,j对数。i,j可以相同。n<=2e5

解法：

根据埃氏筛的原理，我们知道1到n的所有倍数的总数是O(n)级别的。因此，我们可以2到n枚举作为因子的k，那么他的所有倍数两两不互质。显然这种方法枚举出来的数字总数是O(n)级别。

得到了k的倍数后，已经解决了gcd(i,j)!=1的条件。如果对这些倍数位置上的数字两两判断gcd的话一定会超时，因为单单是2的倍数就有1e5，不可以跑\(n^2\)的写法。

那么我们就要快速解决在k倍位置上有多少对贡献。两个数不互质是一定有共同的因子，可以把每个数的因子分离出来，分别计数，用map存储。

如果分离出来了x个2，y个3，z个6，那么以2作为公共因子的有x(x-1)/2对，以3作为公共因子的有y(y-1)/2对。分别计入答案之后发现2，3作为因子的贡献中，6作为因子的贡献重复了，所以还要减去6的贡献z(z-1)。

以此类推，这个问题就要用容斥来解决了。质因子数量是奇数的数字加入答案，是偶数的数字从答案扣除。含有同一质因子多次的的数字跳过。因为我们先统计了质因子的答案，然后要去掉含两个不同质因子的答案，加回来含三个不同质因子的答案。。。

这样我们就解决了k为i，j因子的贡献，同理，k=2与k=3会重复计算k=6部分的贡献，所以也要再跑一边容斥。

这样跑完得到的是不含i，j相同情况的答案，再扫一遍就行了。

#include <bits/stdc++.h>
using namespace std;
#define yaqujiejie yyds
typedef long long ll;
#define int long long
const int N = 2e5+10;
vector<int>prime;//存储素数
vector<int>yz[N];//因子
vector<int>bs[N];//倍数
bool nop[N];//不是素数
bool no[N];//不可
int yzs[N];//质因数数量
void init(){
    for(int i=2;i<N;i++){
        if(!nop[i]){
            if(i*i<N&&i*i>0)no[i*i]=1;
            prime.push_back(i);
            yzs[i]++;
            for(int j=i*2;j<N;j+=i){
                nop[j]=1;
                yzs[j]++;
                ll k=(ll)i*i;
                if(j%k==0)no[j]=1;
            }
        }
        yz[i].push_back(i);
        bs[i].push_back(i);
        for(int j=i*2;j<N;j+=i){
            yz[j].push_back(i);
            bs[i].push_back(j);
        }
    }
}
int a[N];
signed main(){
    ios::sync_with_stdio(false);
    init();
    int n;cin>>n;
    ll ans=0;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int k=2;k<=n;k++){
        unordered_map<int,int>mp;
        for(int j=0;j<bs[k].size();j++){
            for(int u=0;u<yz[a[bs[k][j]]].size();u++){
                mp[yz[a[bs[k][j]]][u]]++;
            }
        }
        ll res=0;
        for(auto p:mp){
            if(no[p.first])continue;
            
            if(yzs[p.first]%2==1)res+=p.second*(p.second-1)/2;
            else res-=p.second*(p.second-1)/2;
        }
        if(no[k])continue;
        if(yzs[k]%2==1)ans+=res;
        else ans-=res;
    }
    for(int i=2;i<=n;i++)if(a[i]!=1)ans++;
    cout<<ans<<"\n";
}