题目链接

Carmichael Numbers UVA - 10006

思路

$$ 先排除素数，再满足 a^{n} mod n = a(0 < a < n) $$

时间复杂度

$$ O(Xlog(X)) $$

代码

#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;
void work(long long x) {
    for (int i = 2; i < x; i++) {
        if (mr.pow_mod(i, x, x) != i) {
            printf("%lld is normal.\n", x);
            return;
        }
    }
    printf("The number %lld is a Carmichael number.\n", x);
}

int main() {
    long long x;

    while (scanf("%lld", &x), x) {
        if (mr.prime(x)) {
            printf("%lld is normal.\n", x);
        } else {
            work(x);
        }
    }
    return 0;
}