首页 > 代码库 > csu 2014 summer training day 2 莫比乌斯反演
csu 2014 summer training day 2 莫比乌斯反演
SPOJ VLATTICE
题意：x,y,z<=1000000，x<=a,y<=b,z<=c,给定a、b、c,求gcd(x,y,z)=1的个数
解释：设 f(n)是gcd(x,y,z)=n的种数，F(n)=n|gcd(x,y,z)的种数
那么F(n)=f(n)+f(2n)....=sigm(f(d)){n|d}
那么根据反演公式 f(n)=sigm(u(d/n)*F(d)){n|d}
我们要求的是f(1)=sigm(u(1)*F(n)+u(2)*F(2n)+u(3)*F(3n).....) kn<=min(a,b,c)
F(d)=(x/d)*(y/d)*(z/d)
依次求和即可，求u(x)部分是模板
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <iostream> 5 #define maxn 1001000 6 #define LL long long 7 using namespace std; 8 9 int K[maxn];10 int C[maxn];11 int U[maxn];12 bool flag[maxn];13 int prim[maxn/3];14 int cnt;15 void culc(){16 cnt=0;17 U[1]=1;18 memset(flag,0,sizeof(flag));19 for(int i=2;i<=1000000;i++){20 if (!flag[i]){21 prim[cnt++]=i;22 U[i]=-1;23 }24 for(int j=0;j<cnt;j++){25 if (i*prim[j]>1000000) break;26 flag[i*prim[j]]=true;27 if (i % prim[j]==0){28 U[i*prim[j]]=0;29 break;30 }else {31 U[i*prim[j]]=-U[i];32 }33 }34 }35 return ;36 }37 LL solve(int N){38 LL ans=0;39 for(int i=1;i<=N;i++){40 LL k=N/i;41 ans=ans+U[i]*k*k*(k+3);42 }43 44 return ans;45 }46 int t;47 int N;48 int main(){49 culc();50 scanf("%d",&t);51 while(t--){52 scanf("%d",&N);53 LL ans=solve(N);54 printf("%lld\n",ans+3);55 }56 return 0;57 }
HDU 1695
题意：
给定b,d,K，求x<=b,y<=d中gcd(x,y)=K的个数，其中gcd(3,5)和gcd(5,3)算一种
分析：和上题类似，关键部分：
if(b > d)swap(b,d); LL ans1=0,ans2=0; for(int i=1; i<=b;i++) ans1+=(LL)U[i]*(b/i)*(d/i); for(int i=1; i<=b;i++) ans2+=(LL)U[i]*(b/i)*(b/i); ans1-=ans2/2;
简要说一下，当i>b时每次都加0，没意义。
当x<=b,y>b的时候，(b,d)只计算了一次
当x<=b,y<=b的时候，(b,d),(d,b)重复出现了两次
所以ans=ans1-ans2/2;
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <iostream> 5 #define maxn 100100 6 #define LL long long 7 using namespace std; 8 9 int U[maxn];10 bool flag[maxn];11 int prim[maxn/3];12 int cnt;13 void culc(){14 cnt=0;15 U[1]=1;16 memset(flag,0,sizeof(flag));17 for(int i=2;i<=100000;i++){18 if (!flag[i]){19 prim[cnt++]=i;20 U[i]=-1;21 }22 for(int j=0;j<cnt;j++){23 if (i*prim[j]>100000) break;24 flag[i*prim[j]]=true;25 if (i % prim[j]==0){26 U[i*prim[j]]=0;27 break;28 }else {29 U[i*prim[j]]=-U[i];30 }31 }32 }33 return ;34 }35 LL solve(int b,int d){36 // LL ans=0;37 // for(int i=1;i<=max(N,M);i++){38 // int m1=min(N/i,M/i);39 // int m2=max(N/i,M/i)-m1;40 // ans=ans+(LL)U[i]*(m1*(m1-1)/2+m1+m1*m2);41 // }42 if(b > d)swap(b,d);43 LL ans1=0,ans2=0;44 for(int i=1; i<=b;i++)45 ans1+=(LL)U[i]*(b/i)*(d/i);46 for(int i=1; i<=b;i++)47 ans2+=(LL)U[i]*(b/i)*(b/i);48 ans1-=ans2/2;49 return ans1;50 }51 int t;52 int N,M,K;53 int main(){54 culc();55 scanf("%d",&t);56 for(int cas=1;cas<=t;cas++){57 scanf("%d%d%d%d%d",&N,&N,&M,&M,&K);58 LL ans;59 if (K==0) ans=0;60 else ans=solve(N/K,M/K);61 printf("Case %d: %I64d\n",cas,ans);62 }63 return 0;64 }
HYSBZ 2818
题意：给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对.时限很长
分析：这里要求的gcd是素数，我们只要枚举N以内的素数即可，再求出相应的gcd=prim即可
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <iostream> 5 #define maxn 10010000 6 #define LL long long 7 using namespace std; 8 9 int U[maxn];10 bool flag[maxn];11 int prim[maxn/3];12 int cnt;13 void culc(){14 cnt=0;15 U[1]=1;16 memset(flag,0,sizeof(flag));17 for(int i=2;i<=10000000;i++){18 if (!flag[i]){19 prim[cnt++]=i;20 U[i]=-1;21 }22 for(int j=0;j<cnt;j++){23 if (i*prim[j]>10000000) break;24 flag[i*prim[j]]=true;25 if (i % prim[j]==0){26 U[i*prim[j]]=0;27 break;28 }else {29 U[i*prim[j]]=-U[i];30 }31 }32 }33 return ;34 }35 LL solve(int N){36 LL ans=0;37 for(int i=1;i<=N;i++){38 ans=ans+(LL)U[i]*(N/i)*(N/i);39 }40 return ans;41 }42 int t;43 int N,M,K;44 int main(){45 culc();46 scanf("%d",&N);47 LL ans=0;48 for(int i=0;i<cnt;i++) {49 if (prim[i]>N) break;50 ans+=solve(N/prim[i]);51 }52 printf("%lld\n",ans);53 return 0;54 }
HYSBZ 2005
题意：一共有n列，每列有m棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标(x, y)来表示，其中x的范围是1至n，表示是在第x列，y的范围是1至m，表示是在第x列的第y棵。 由于能量汇集机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是(0, 0)。 能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有k棵植物，则能量的损失为2k + 1。例如，当能量汇集机器收集坐标为(2, 4)的植物时，由于连接线段上存在一棵植物(1, 2)，会产生3的能量损失。注意，如果一棵植物与能量汇集机器连接的线段上没有植物，则能量损失为1。现在要计算总的能量损失。
分析：很好的一道题，代码中优详细说明
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <iostream> 5 #define maxn 100000 6 #define LL long long 7 using namespace std; 8 9 LL F[maxn+100];10 int main(){11 LL n,m;12 while(~scanf("%lld%lld",&n,&m)){13 if (n>m) swap(n,m);14 LL ans=0;15 for(int i=n;i>=1;i--){//我们要保证每次能除掉2i,3i...即比i大的F(x)，所以i只能从大向小求取16 F[i]=(n/i)*(m/i);//gcd(x,y)=i,2i,3i....的数量17 for(int j=2*i;j<=n;j+=i){//枚举18 F[i]-=F[j];//去除掉gcd(x,y)=2i,3i,4i....的部分19 }20 //F[i]=gcd(x,y)=i的数量21 ans+=F[i]*(2*i-1);//既然是取得的第i项，那么这些22 }23 printf("%lld\n",ans);24 }25 return 0;26 }
HYSBZ 2301（综合）
题意：对于给出的n个询问，每次求有多少个数对(x,y)，满足a≤x≤b，c≤y≤d，且gcd(x,y) = k，gcd(x,y)函数为x和y的最大公约数。
分析：化简：gcd等式两边同除以k，求gcd=1即可，集合间的关系，再用分段优化
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <iostream> 5 #define maxn 50000 6 #define LL long long 7 using namespace std; 8 9 int U[maxn+100];10 bool flag[maxn+100];11 int prim[maxn/3+100];12 int cnt;13 void culc(){14 cnt=0;15 U[1]=1;16 memset(flag,0,sizeof(flag));17 for(int i=2;i<=maxn;i++){18 if (!flag[i]){19 prim[cnt++]=i;20 U[i]=-1;21 }22 for(int j=0;j<cnt;j++){23 if (i*prim[j]>maxn) break;24 flag[i*prim[j]]=true;25 if (i % prim[j]==0){26 U[i*prim[j]]=0;27 break;28 }else {29 U[i*prim[j]]=-U[i];30 }31 }32 }33 return ;34 }35 int sum[maxn+100];36 //找[1,n],[1,m]内互质的数的对数37 LL solve(int n,int m){38 LL ans=0;39 if (n>m) swap(n,m);40 for(int i=1,last=0;i<=n;i=last+1){41 last=min(n/(n/i),m/(m/i));42 ans+=(LL)(sum[last]-sum[i-1])*(n/i)*(m/i);43 }44 return ans;45 }46 47 int t;48 int a,b,c,d,k;49 int main(){50 culc();51 sum[0]=0;52 for(int i=1;i<=maxn;i++){53 sum[i]=sum[i-1]+U[i];54 }55 scanf("%d",&t);56 for(int cas=1;cas<=t;cas++){57 scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);58 LL ans;59 a--,c--;60 ans=solve(b/k,d/k)-solve(a/k,d/k)-solve(b/k,c/k)+solve(a/k,c/k);61 printf("%lld\n",ans);62 }63 return 0;64 }
ZOJ 3435
题意：求gcd(x,y,z)=1的个数，但是卡时限，要分段优化，注意代码
1 #include <iostream> 2 #include <string.h> 3 #include <stdio.h> 4 #include <iostream> 5 #define maxn 1000000 6 #define LL long long 7 using namespace std; 8 9 int U[maxn+100];10 bool flag[maxn+100];11 int prim[maxn/3+100];12 LL sum[maxn+100];13 int cnt;14 void culc(){15 cnt=0;16 U[1]=1;17 memset(flag,0,sizeof(flag));18 for(int i=2;i<=maxn;i++){19 if (!flag[i]){20 prim[cnt++]=i;21 U[i]=-1;22 }23 for(int j=0;j<cnt;j++){24 if (i*prim[j]>maxn) break;25 flag[i*prim[j]]=true;26 if (i % prim[j]==0){27 U[i*prim[j]]=0;28 break;29 }else {30 U[i*prim[j]]=-U[i];31 }32 }33 }34 sum[0]=0;35 for(int i=1;i<=maxn;i++) sum[i]=sum[i-1]+U[i];36 return ;37 }38 LL solve(int a,int b,int c){39 int m=max(a,b);m=max(m,c);40 LL ans=0;41 int Inf=1000100;42 for(int i=1,last;i<=m;i=last+1){43 last=Inf;44 if (i<=a) last=min(last,a/(a/i));45 if (i<=b) last=min(last,b/(b/i));46 if (i<=c) last=min(last,c/(c/i));47 // cout<<"last="<<last;48 ans+=(sum[last]-sum[i-1])*(((LL)a/last+1)*((LL)b/last+1)*((LL)c/last+1)-1);49 // cout<<"ans="<<ans<<endl;50 }51 return ans;52 }53 int a,b,c;54 int main(){55 culc();56 while(scanf("%d%d%d",&a,&b,&c)!=EOF){57 a--;b--;c--;58 LL ans=solve(a,b,c);59 printf("%lld\n",ans);60 }61 return 0;62 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。