POJ3641 UVA11287 HDU1905 Pseudoprime numbers【素数判定+快速模幂】

问题链接：POJ3641 UVA11287 HDU1905 Pseudoprime numbers。

问题简述：参见上述链接。

问题分析：

这个问题是验证伪素数问题。p是伪素数的条件是，p不是素数并且满足a^p = a (mod p)。

伪素数是数论中与费尔马小定理有关的一个重要概念。

程序说明：

函数isprime()不是一个真正意义上的素数判断函数，只进行奇数判定，对于本题条件是没有问题的。

函数powermod()是模幂计算函数。

AC的C++语言程序如下：

/* POJ3641 UVA11287 HDU1905 Pseudoprime numbers */

#include <iostream>
#include <cmath>

using namespace std;

typedef unsigned long long ULL;

// 试除法判断一个数是否为素数
bool isprime(ULL n)
{
    ULL end2, i;

    end2 = sqrt(n);
    for(i=3; i<=end2; i+=2) {
        if(n % i == 0)
            break;
    }

    return i > end2;
}

// 模幂计算
ULL powermod(ULL a, ULL n, ULL m)
{
    ULL res = 1LL;
    while(n) {
        if(n & 1LL) {        // n % 2 == 1
            res *= a;
            res %= m;
        }
        a *= a;
        a %= m;
        n >>= 1;
    }
    return res;
}

int main()
{
    ULL p, a;

    while(cin >> p >> a && (p || a)) {
        if(!isprime(p) && powermod(a, p, p) == a % p)
            cout << "yes" << endl;
        else
            cout << "no" << endl;
    }

    return 0;
}