题目链接

Pseudoprime numbers POJ - 3641

思路

$$ 素性测试，快速幂 $$

时间复杂度

$$ O(log(P)) $$

代码

#include <cstdio>
#include <vector>

using namespace std;

class Miller_Rabin {
public:
    vector<long long> p;
    Miller_Rabin() {
        p.push_back(2);
        p.push_back(3);
        p.push_back(5);
        p.push_back(7);
        p.push_back(11);
        p.push_back(13);
        p.push_back(17);
        p.push_back(19);
        p.push_back(23);
        p.push_back(29);
        p.push_back(31);
        p.push_back(37);
    }



    long long mul_mod(long long a, long long b, long long mod) {
        long long tmp = (long double) a * b / mod;
        return ((a * b - tmp * mod) % mod + mod) % mod;
    }

    long long pow_mod(long long a, long long b, long long mod) {
        long long res = 1;
        res %= mod;
        while (b) {
            if (b & 1) {
                res = mul_mod(res, a, mod);
            }
            a = mul_mod(a, a, mod);
            b >>= 1;
        }
        return res;
    }

    bool prime(long long n) {
        for (int i = 0; i < (int)p.size(); i++) {
            if (p[i] == n) {
                return true;
            } else if (p[i] > n) {
                return false;
            }
            long long tmp = pow_mod(p[i], n - 1, n);
            long long tnp = n - 1;
            if (tmp != 1) {
                return false;
            }
            while (tmp == 1 && tnp % 2 == 0) {
                tnp /= 2;
                tmp = pow_mod(p[i], tnp, n);
                if (tmp != 1 && tmp != n - 1) {
                    return false;
                }
            }

        }
        return true;
    }
};
Miller_Rabin mr;


int main() {
    int x, y;
    while (scanf("%d%d", &x, &y), x + y) {
        if (mr.prime(x)) {
            puts("no");
        } else {
            printf("%s\n", mr.pow_mod(y, x, x) == y ? "yes" : "no");
        }
    }
    return 0;
}