POJ 1091

这题确实是好。

其实是求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 __int64

using 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

最新文章

热门文章