51Nod1675 序列变换 数论 莫比乌斯反演

原文http://www.cnblogs.com/zhouzhendong/p/8665675.html

题目传送门 - 51Nod1675

题意

  给定序列$a,b$,让你求满足$\gcd(x,y)=1,a_{b_x}=b_{a_y}$的$(x,y)$的个数。

题解

  我们先考虑没有$gcd(x,y)=1$的情况。

  仔细一看发现$a_{b_x}=b_{a_y}$是个障眼法,跟你绕来绕去。

  弄个新的$A,B$序列,其中$A_x=a_{b_x},B_x=b_{a_x}$。然后就把这个条件变成了$A_x=B_y$。舒服多了。

  然后我们可以把其中一个序列信息放进桶里面,然后另一个随便弄几下,就可以$O(n)$搞定了。

  考虑到$gcd(x,y)=1$。于是这里要用到莫比乌斯反演套路:倍数反演。

  设$f(i)$表示$i=gcd(x,y)$的满足条件的答案数。

  设$F(i)$表示$i|gcd(x,y)$的满足条件的答案数。

  于是这里可以放上倍数反演的式子:

  $$F(n)=\sum_{n|d}f(d)\Longrightarrow f(n)=\sum_{n|d}\mu(\frac{d}{n})F(d)$$

  这里只需要求$f(1)=\sum_{i=1}^{n}\mu(i)*F(i)$。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
int n,a[N],b[N],_a[N],_b[N],tax[N];
int prime[N],u[N],pcnt=0;
LL F[N];
bool f[N];
void get_prime(int n){
memset(f,true,sizeof f);
u[1]=1,f[0]=f[1]=0;
for (int i=2;i<=n;i++){
if (f[i])
prime[++pcnt]=i,u[i]=-1;
for (int j=1;j<=pcnt&&i*prime[j]<=n;j++){
f[i*prime[j]]=0;
if (i%prime[j])
u[i*prime[j]]=-u[i];
else {
u[i*prime[j]]=0;
break;
}
}
}
}
int main(){
scanf("%d",&n);
get_prime(n);
for (int i=1;i<=n;i++)
scanf("%d",&_a[i]);
for (int i=1;i<=n;i++)
scanf("%d",&_b[i]);
for (int i=1;i<=n;i++)
a[i]=_a[_b[i]],b[i]=_b[_a[i]];
memset(tax,0,sizeof tax);
LL ans=0;
for (int i=1;i<=n;i++){
F[i]=0;
for (int j=i;j<=n;j+=i)
tax[a[j]]++;
for (int j=i;j<=n;j+=i)
F[i]+=tax[b[j]];
for (int j=i;j<=n;j+=i)
tax[a[j]]--;
ans+=F[i]*u[i];
}
printf("%lld",ans);
return 0;
}

  

上一篇:Hibernate 更新部分字段的实现


下一篇:转:IIS 应用程序池 内存 自动回收