题目
给定长为n(n<=2e5)的1-n的排列p,
求(i,j)(1<=i<=j<=n)对的数量,满足gcd(i,j)≠1且gcd(pi,pj)≠1
思路来源
官方题解
题解
参考莫比乌斯函数mu,定义一个新函数,
新函数需要满足n=1的时候对因子求和为0,大于1的时候对因子求和为1,
就能将gcd(i,j)≠1展开为新函数了
然后发现,实际上就是,
之前n>=2的时候,因子mu之和为0,
由于gcd不能为1,要忽略mu[1]的贡献,
那么0减掉mu[1]之后是-1,取反之后即为1,
所以相当于把之前奇偶因子的符号取反
枚举i和i的倍数j,所有倍数j需要反演得到i固定时的答案,
此时这些j已经满足gcd(j1,j2)≠1,第二个条件需要再套一次反演
把这些pj塞入vector,再做一次反演即可
一共有x个数时,任意取两个,可以重复取,
等价于有x个数和一个空位,这x+1个数取两个
取到了一个数和一个空位的时候,就认为是取了两次相同的数
代码1(容斥)
#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int n,p[N],a[N];
vector<int>fac[N],tmp;
map<int,ll>bs;
ll dp[N],f[N],res;
//x内任取两个 gcd大于1的(i,j)方案数
ll cal(vector<int>&x){
bs.clear();
for(auto &v:x){
for(auto &d:fac[v]){
bs[d]++;
}
}
int c=0;
for(auto &x:bs){
x.se=1ll*x.se*(x.se+1)/2;
a[++c]=x.fi;
f[x.fi]=x.se;
}
ll ans=0;
//printf("c:%d v:%d\n",c,a[1]);
per(i,c,1){
int v=a[i];
if(v==1)break;
ll w=f[v];
for(auto &d:fac[v]){
f[d]-=w;
}
ans+=w;
}
return ans;
}
int main(){
sci(n);
rep(i,1,n)sci(p[i]);
rep(i,1,n){
for(int j=i;j<=n;j+=i){
fac[j].pb(i);
}
}
per(i,n,2){
tmp.clear();
for(int j=i;j<=n;j+=i){
tmp.pb(p[j]);
}
dp[i]=cal(tmp);
//printf("i:%d dp1:%lld\n",i,dp[i]);
for(int j=2*i;j<=n;j+=i){
dp[i]-=dp[j];
}
//printf("i:%d dp2:%lld\n",i,dp[i]);
res+=dp[i];
}
printf("%lld\n",res);
return 0;
}
代码2(反演)
//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=2e5+10;
int n,p[N],a[N],mu[N];
vector<int>fac[N],tmp;
ll dp[N],bs[N],f[N],res;
//x内任取两个 gcd大于1的(i,j)方案数
ll cal(vector<int>&x){
for(auto &v:x){
for(auto &d:fac[v]){
if(!mu[d])continue;
bs[d]++;
}
}
ll ans=0;
for(auto &v:x){
for(auto &d:fac[v]){
if(!bs[d] || d==1 || !mu[d])continue;
bs[d]=1ll*bs[d]*(bs[d]+1)/2;
ans-=mu[d]*bs[d];
bs[d]=0;
}
}
return ans;
}
int main(){
sci(n);
rep(i,1,n)sci(p[i]);
mu[1]=1;
rep(i,1,n){
fac[i].pb(i);
for(int j=2*i;j<=n;j+=i){
mu[j]-=mu[i];
fac[j].pb(i);
}
}
per(i,n,2){
if(!mu[i])continue;
tmp.clear();
for(int j=i;j<=n;j+=i){
tmp.pb(p[j]);
}
dp[i]=cal(tmp);
res-=mu[i]*dp[i];
//printf("i:%d dp1:%lld\n",i,dp[i]);
// for(int j=2*i;j<=n;j+=i){
// dp[i]-=dp[j];
// }
// //printf("i:%d dp2:%lld\n",i,dp[i]);
// res+=dp[i];
}
printf("%lld\n",res);
return 0;
}