本文共 1534 字，大约阅读时间需要 5 分钟。

快速幂：快速幂就是所求的幂次方过大，导致代码所用的时间超限。

如：求2^3,3的二进制是11，(n&1)判断次方数的二进制是否为1，n>>1,向右进位1：

代码：

k=1,t=n;while(n)	{
   		if(n&1)//判断n的最后一位二进制不为0		{
   			k=k*m;		}		n=n>>1;		m=m*m;	}

题目描述：

Fermat’s theorem states that for any prime number p and for any integer a > 1, ap = a (mod p). That is, if we

raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.) Given 2 < p ≤ 1000000000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input

Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.

Output

For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".

Sample Input

3 210 3341 2341 31105 21105 30 0

Sample Output

nonoyesnoyesyes

解题思路：这个题理解起来就是两个函数去判断，对应输出yes/no,首先判断这个数是否为素数，然后再判断(a^p)%p==a就可以了，不过这个幂次方就是需要快速幂。

程序代码：

#include
   
    #include
    
     int  fn(long long n){
   	long long i,j,k;	k=sqrt(n);	for(i=2;i<=k;i++)	{
   		if(n%i==0)			return 0;	}	return 1;}int f(long long n,long long m){
   	long long k,a,t;	k=1,t=n;	while(n)	{
   		if(n&1)		{
   			k=(k*m)%t;		}		n=n>>1;		m=(m*m)%t;	}	return k;}int main(){
   	long long i,j,k,m,n;	while(scanf("%lld%lld",&n,&m)!=EOF)	{
   		if(n==0&&m==0)			break;		if(fn(n)==1)			printf("no\n");		else		{
   			k=f(n,m);			if(k==m)				printf("yes\n");			else				printf("no\n");		}	}	return 0;}
    
   

转载地址：http://lexzi.baihongyu.com/