Pseudoprime numbers（快速幂模板题）

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 2
10 3
341 2
341 3
1105 2
1105 3
0 0

Sample Output

no
no
yes
no
yes
yes

题意描述：

输入一对p和a，如果p是素数，输出no；如果p不是素数，判断a^p对p取余是否等于a。

解题思路：

套快速幂模板直接AC

代码：

#include<bits/stdc++.h>
long long int qpow(long long int a,long long int b)//快速幂模板
{
    long long int ans = 1,t=b;
    while(b){
        if(b&1)        //如果n的当前末位为1
            ans=(ans*a)%t;  //ans乘上当前的a
        a=(a*a)%t;        //a自乘
        b >>= 1;       //n往右移一位
    }
    return ans%t;
}
long long int prime(long long int n)
{
    long long int i,k;
    if(n== 0) 
	return 0;
    k=sqrt(n);
    for(i=2;i<=k;i++)
    {
        if(n%i==0) 
		return 0;
    }
    return 1;
}
int main()
{

    long long int p,a;
    while(scanf("%lld %lld",&p,&a) &&p+a)
    {
        if(prime(p))
		printf("no\n");
        else
        {
            if(qpow(a,p) == a)
			printf("yes\n");
            else
            printf("no\n");
        }

    }
}