算法模板目录 ：个人算法模板

例题：好想会数学啊

std::ostream &operator<<(std::ostream &os, __int128 n) {
    std::string s;
    while (n) {
        s += '0' + n % 10;
        n /= 10;
    }
    std::reverse(s.begin(), s.end());
    return os << s;
}
__int128 mul(__int128 a, __int128 b, __int128 M) {
    a = (a % M + M) % M;
    b = (b % M + M) % M;
    __int128 ans = 0;
    while (b) {
        if (b & 1) {
            ans += a;
            if (ans >= M) {
                ans -= M;
            }
        }
        a <<= 1;
        if (a >= M) {
            a -= M;
        }
        b >>= 1;
    }
    return ans;
}
__int128 power(__int128 n, __int128 k, __int128 M) {
    __int128 ans = 1;
    while (k) {
        if (k & 1) {
            ans = mul(ans, n, M);
        }
        n = mul(n, n, M);
        k >>= 1;
    }
    return ans;
}
bool check(__int128 x,__int128 M){
    __int128 mid = power(x, M - 1, M);
    if (mid != 1) return false;
    __int128 n = M - 1;
    while (n % 2 == 0 && mid == 1) {
        n >>= 1;
        mid = power(x, n, M);
    }
    if (mid == 1 || mid == M - 1) return true;
    return false;
}
bool Miller_Rabin(LL x) {
    vector<int> prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47};
    if (x <= 47) {
        for (int i = 0; i < 15; i++) {
            if (prime[i] == x) {
                return true;
            }
        }
        return false;
    }
    for (int i = 0; i < 15; i++) {
        if (!check(prime[i], x)) {
            return false;
        }
    }
    return true;
}