UVa11287 Pseudoprime numbers

問題
http://uva.onlinejudge.org/external/112/11287.html

概要
Fermatの小定理： $a^p \equiv a (mod p)$ （または $a^{p-1} \equiv 1 (mod p)$ ）
であるが、pが素数でないときこの関係式が成り立つ p を基数 a における pseudoprimes という。
p が基数 a における pseudoprimes であるかどうか判定せよ。

解法
そのまま。ただし、べき乗は蟻本の mod_pow() を使うと良い。

※mod_pow() について（蟻本P.116とほぼ同じ内容）
$q$ が偶数のとき、 $x^q=((x^2)^{q/2})$ より、 $n/2$ に帰着可能。 $q$ が奇数の場合は $x^q=((x^2)^{q/2})\times x$ （ $q$ を $2$ で整数除算しているので $x$ が一個余る）となり、同様に $n/2$ に帰着する。この再帰により $q$ は一度の処理ごとに半分以下になるので、O(log n) でべき乗が求まる。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

// prime
bool isPrime(int a) { for(int i=2; i*i <=a; i++) if(a%i == 0) return false; return true; }

ll mod_pow(ll x, ll q, ll MOD) {
  if(q == 0) return 1;
  ll res = mod_pow(x*x % MOD, q/2, MOD);
  if(q & 1) res = res * x % MOD;
  return res;
}

int main() {
  
  ll p, a;
  while(cin >> p >> a && (p|a)) {
    bool yes = 1;
    yes &= !isPrime(p);
    yes &= mod_pow(a, p, p) == a;
    if(yes) {
      cout << "yes" << endl;
    }
    else {
      cout << "no" << endl;
    }
  }
  
  return 0;
}