読者です 読者をやめる 読者になる 読者になる

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 xq2で整数除算しているので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;
}