聪明的猴子

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 153   Accepted Submission(s) : 53

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

Input

Output

Sample Input

3
2 3
4 8
5 13

Sample Output

8
3840
371292

Source

题解：因为每一次从卡片选一张出来。就是说。每一张卡片都可以被选择不限定次数。

则x1*ak[1]+x2*ak[2]+……+xn*ak[n] +xn+1*m = 1

则可知ak[1]……ak[n],m之间一定不能有互质的数。。

所以我们先求出不符合的情况。就是说ak[1]……ak[n],m之间的两两有约数大于1。。

则他们有共同的约数。。这些约数只能是质数。。（因为不是质数的约数可以分割成质数相乘。如6 = 2*3）

2 3 5 7……。就是m的所有质约数。。

然后求出共同是2约数的个数。3的个数。。等等。但是还要减去重合的现象。。比如6的个数。。

这就要用到容斥定理。。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<math.h>

using namespace std;
#define ll __int64
ll ans,a,b;
int p[] = {2,3,5,7,11,13,17,19,23};
int ak[2000],len,bb[2000];
void totalnum(__int64 x) //参考poj高效互质 
 {
	__int64 i,j;
	int total=0;
 	for(i=2;i*i<=x;i++)
	{
 		if(x%i==0)
 		{
 			while(x%i==0)
 				x=x/i;
 			ak[total]=i;
 			total++;
 		}
 	}
 	if(x!=1)
 	{
 		ak[total]=x;
 		total++;
 	}
 	len = total;
 }
int ok(int b)
{
	int j = 0,k = 0;
	while(b>1) {
		if(b%p[j]==0) {
		b/=p[j];
		if(k==0 || ak[k-1]!=p[j])
		ak[k++] = p[j];
	    }
	    else
	    j++;
	}
	return k;
}
ll po(ll a,ll b)
{
	int i;
	ll an = 1;
	for(i=0;i<b;i++)
		an*=a;
	return an;
}
void work(int k,int t)
{
	int i,va = 1;
	if(k==len) {
		for(i=0;i<t;i++) {
			va*=bb[i];
		}
		if(t==0) return;
		if(t%2)
		ans-=po(b/va,a);
		else
		ans+=po(b/va,a);
		return ;
	}
	work(k+1,t);
	bb[t] = ak[k];
	work(k+1,t+1);
	
}

int main()
{
   	int n,i,j;
	//ll a,b;
   	scanf("%d",&n);
   	while(n--){
   		scanf("%I64d%I64d",&a,&b);
        totalnum(b);
        ans = po(b,a);
		//len = ok(b);
		work(0,0);
        
        printf("%I64d\n",ans);
   	}
	
    return 0;
	
}

携程——聪明的猴子 （容斥定理）,布布扣,bubuko.com

携程——聪明的猴子 （容斥定理）

原文：http://blog.csdn.net/min_lala/article/details/23826337