第一行一个数n(1<=n<=100000)。 接下来一行n个数，表示ai(1<=ai<=n)。 接下来一行n个数，表示bi(1<=bi<=n)。
一行表示答案
3 1 1 1 1 1 1
7
没有gcd(x,y)=1直接用个桶O(n)统计就好了
然后用到了容斥原理，所有数对(有公因子1)-有1个公因子+有2个不同公因子-有3个不同公因子......
前面的系数就是莫比乌斯函数啊
接下来我们只要计算出x,y都为t的倍数时的答案，再与u[t]相乘累加进答案就可以了。
复杂度O(nlogn),不能用memset哦
PS：为什么有多个p的不算呢？因为这个在一个p时已经算过了
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> using namespace std; typedef long long ll; const int N=1e5+5; inline int read(){ char c=getchar();ll x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f; } int n,a[N],b[N]; bool notp[N]; int p[N],mu[N]; void sieve(int n){ mu[1]=1; for(int i=2;i<=n;i++){ if(!notp[i]) p[++p[0]]=i,mu[i]=-1; for(int j=1;j<=p[0]&&i*p[j]<=n;j++){ notp[i*p[j]]=1; if(i%p[j]==0) break; mu[i*p[j]]=-mu[i]; } } } ll ans=0; int c[N]; ll calc(int t){ ll _=0; for(int i=t;i<=n;i+=t) c[a[b[i]]]++; for(int i=t;i<=n;i+=t) _+=c[b[a[i]]]; for(int i=t;i<=n;i+=t) c[a[b[i]]]--; return _; } void solve(){ for(int i=1;i<=n;i++) if(mu[i]) ans+=calc(i)*mu[i]; printf("%lld",ans); } int main(){ freopen("in","r",stdin); n=read(); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++) b[i]=read(); sieve(n); solve(); }
51Nod 欢乐手速场1 B 序列变换[容斥原理 莫比乌斯函数]
原文：http://www.cnblogs.com/candy99/p/6366928.html