WC 第一课堂讲字符串哈希和快速幂？

第一讲堂内容：

上午：

LOJ143. 质数判定

Miller-Rabin 模板。

Fermart 小定理：

若 p 是质数， a 是小于 p 的正整数，则 a^{p-1}\equiv 1 \pmod p。

反之，若 a^{p-1}\equiv 1 \pmod p 成立，则 p 有很大概率成立。

总结：若 a^{p-1} \not\equiv 1 \pmod p 则 p 是合数。若 a^{p-1}\equiv 1 \pmod p，则 p 可能是质数。

二次探测定理：

当 p 是质数时， x^2\equiv 1 \pmod p 的根只有 x \equiv 1 和 x \equiv n - 1.

合数情况则不然。称 x \equiv \pm 1 为 x^2\equiv 1 \pmod p 的平凡根。其余解为非平凡根。

若 2^{p-1}\equiv 1 \pmod p 且 p 是合数，则我们称 p 为伪素数。

若 \forall a < p, a^{p-1} \equiv 1 \pmod p ，且 p 为合数，则称 p 为强伪素数（或称 Carmichael 数）。

Miller-Rabin 素性测试：

首先易证明除 2 以外的偶数是合数。

结合 Fermart 小定理与二次探测定理。

注意到绝大部分素数均为奇数，则 p - 1 为偶数。符合二次探测定理应用条件。

构造数列 2^1 \times p_1, 2^2 \times p_2, ... 2^n \times p_n (2^i \times p_i = p) 。

若 a^{p_{i-1}}\equiv 1 \pmod{p} 且 2^{p_i} \not\in \{1,-1\} \pmod{p} 则 p 是合数。

#include <bits/stdc++.h>
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << #x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define ms(x) memset(x, 0, sizeof x)
#define int __int128
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

void file() {
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w+", stdout);
}

int qpow(int a, int b, int m) {
    int res = 1, base = a;
    while(b) {
        if(b & 1) res = base * res % m;
        base = base * base % m; b >>= 1;
    }
    return res;
}

bool MillerRabin(int x) {
    if(x == 0 || x == 1) return false;
    if(x == 2) return true;
    if(x % 2 == 0) return false;
    for(int i = 1; i <= 10; i++) {
        int it = (((int)rand() << 31) | rand()) % (x - 2) + 2;
        int t = (x - 1) / 2;
        while(t > 0) {
            int res = qpow(it, t, x);
            if(res == x - 1) break;
            else if(res != 1) return false;
            else if(res == 1) {
                if(t % 2 == 1) break;
                else t /= 2;
            }
        }
    }
    return true;
}

signed main() {
#ifdef LOCAL
    file();
#endif
    unsigned long long x;
    while(~scanf("%lld", &x)) {
        puts(MillerRabin(x) ? "Y" : "N");
    }

    return 0;
}

下午：

记nm。