#P05804. 伪素数

---

这道题考的是费马小定理和快速幂。

思路:

首先， 我们要判断输入的数是否为素数。如果是，说明它必定不是基于a的伪素数。(因为它本身就是一个素数啊！)

如果不是，就要用到费马小定理了。因为如果P是一个素数，则对于a（1≤a≤P-1）， 都有a^P ≡a (Mod P)，所以就相当于a % p == (a ^ p) % p。那么我们就只需要用快速幂把(a ^ p) % p算出来,再判断是否等于a % p即可。如果相等,说明这个数虽然是合数但满足费马小定理，为伪素数，输出"yes"。否则，说明 不是伪素数，输出“no”。

代码:

#include
using namespace std;
long long p,a,t;
bool isp(long long n)
{
  if(n < 2) return 0;
  if(n == 2) return 1;
  for(long long i = 2; i <= n / i; i++)
    if(n % i == 0)
      return 0;
  return 1;
}
long long mi(long long a,long long b,long long p)
{
  long long ans = 1;
  while(b)
  {
    if(b % 2 == 1) ans *= a,ans %= p;
    b /= 2;
    a *= a;
    a %= p;
  }
  return ans;
}
int main()
{
  while(cin>>p>>a)
  {
    if(p == 0 && a == 0) break;
    if(isp(p) == 1) cout<<"no"<
    else
    {
      t = mi(a,p,p);
      if(t == a % p) cout<<"yes"<
      else cout<<"no"<
    }
  }
  return 0;
}

p.s:望ZY老师康到啊！——weq