首页 > 代码库 > POJ 1091

POJ 1091

2024-07-21 03:14:42   225人阅读

这题确实是好。

其实是求x1*a1+x2*a2+....M*xn+1=1有解的条件。很明显，就是(a1,a2,...M)=1了。然后，可以想象，直接求有多少种，很难，所以，求出选择哪些数一起会不与M互质。。。好吧，思路就到这里了。。。T_T

经过人提示，若（a1,a2,,,,an）与M不互质，则最大公约数中必定包含M中的质数。啊，愰然大悟，这不是显而易见的吗？为什么我想不到？

所以，先求出M包含哪些质数，那么，选出其中一些包含该质数的数组成数列不就好了？这很容易就能想到容斥原理了，因为选出一些数，使它具有性质P1，又选出另一些集合使它具有P2,P3....，最终求至少包含一个性质的集合。

那么，能被1~M中能被P1整除的个数为【M/p1】,以此类推。。。

由容斥原理公式

如此，从M^N中减去就可以了。

#include <iostream>#include <cstdio>#include <algorithm>#define LL __int64using namespace std;LL prime[50],l;LL n,m;LL Power(LL m,LL n){	LL ret=1;	for(int i=1;i<=n;i++){		ret=ret*m;	}	return ret;}void wprime(LL m){	if(m%2==0){		prime[l++]=2;		while(m%2==0)		m/=2;	}	for(LL i=3;i*i<=m;i+=2)	if(m%i==0){		prime[l++]=i;		while(m%i==0)		m/=i;	}	if(m>1)	prime[l++]=m;}void Nest(LL p, LL re, LL c,LL &res){	if(c==0){		//	cout<<re<<endl;			res+=Power(m/re,n);		return ;	}	else{		for(LL i=p;i<l;i++){			Nest(i+1,re*prime[i],c-1,res);		}	}}LL work(LL c){	LL res=0;	for(LL i=0;i<l;i++){		Nest(i+1,prime[i],c-1,res);	}	return res;}int main(){	while(scanf("%I64d%I64d",&n,&m)!=EOF){		l=0;		LL al=Power(m,n);		wprime(m);		LL c=1;		for(LL i=1;i<=l;i++){			c*=-1;			LL res=work(i);			al+=(c*res);		}		printf("%I64d\n",al);	}	return 0;}

 

POJ 1091


联系
我们