Poj 3641: Pseudoprime numbers

poj3641.md

Poj 3641: Pseudoprime numbers

題目

分析

p is pseduoprime <-> p is not prime && a^p % p = a

AC Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long ll;

bool is_prime(const int n) {
    if (n == 0 || n == 1)
        return false;
    if (n == 2 || n == 3 || n == 5)
        return true;
    if (n % 2 == 0 || n % 3 == 0 || n % 5 == 0)
        return false;

    int sqn = int(sqrt(n));
    for (int i = 7; i <= sqn; i += 2)
        if (n % i == 0)
            return false;

    return true;
}

ll pow_mod(const ll a, const ll b, const ll c) {
    // a^b % c
    if (b == 0)
        return 1;
    if (b & 1)
        return a * pow_mod(a * a % c, b / 2, c) % c;
    return pow_mod(a * a % c, b / 2, c) % c;
}

int main() {
    int p, a;
    while (scanf("%d %d", &p, &a)) {
        if (p == 0 && a == 0) break;

        if (!is_prime(p) && pow_mod(a, p, p) == a)
            puts("yes");
        else
            puts("no");
    }
}