Description：

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不是素数并且p^a是否等于a，若等于则输出yes，否则输出no。

这个题主要用到快速幂，其他就比较简单了，注意类型一定要是long long！！！（因为结果非常大）

程序代码：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
long long prime(long long x)
{
  for(int i=2;i<=sqrt(x);i++)
    if(x%i==0)
      return 0;
  return 1;
}
long long quickmul(long long a,long long b)
{
  long long ans=1;
  long long m=b;
  while(m)
  {
    if(m&1)//等价于m%2==1 
      ans=(ans*a)%b;
    a=(a*a)%b;
    m>>=1;//等价于m=m/2 
  }
  return ans;
}
int main()
{
  long long p,a;
  while(scanf("%lld %lld",&p,&a)&&(p+a))
  {
    if(prime(p))
      printf("no\n");
    else if(quickmul(a,p)==a)
      printf("yes\n");
    else
      printf("no\n");
  }
  return 0;
}