题解：P10404 「XSOI-R1」原神数

· · 题解

前置知识：Miller_Rabin 算法。

显然我们需要判断一个数是不是质数。

令判断的数为 x，显然我们可以找一个质数 p，当 x=p 时，x 为质数，当 p\mid x 时，x 为合数。

然后判断 p^{x-1}\bmod x 是否为 1，如果不是，则 x 必然不是质数。

虽然但是，如果是，x 也必然不是质数。

否则，考虑二次探测定理。

显然 x^2\equiv1\pmod p 时，x\equiv 1\pmod p 或 x\equiv p-1\pmod p。

证明挺简单，这里懒得证。

先用 k 记录 x-1。

然后先将 k 除以 2，令 t=p^k\bmod x。

如果 t\not =1 且 t\not = x-1，则根据二次探测定理，x 不是质数。

若 t=x-1，则无法继续用二次探测定理，认为 x 是质数。

否则一直除，直至 k 为奇数，此时默认其为质数。

很显然这个东西有可能是错的，于是考虑多测几个 p，提高准确率。

复杂度 \mathcal{O}(c\log n)，c 为选的质数个数，总复杂度远远胜过 \mathcal{O(\sqrt n)}。

经过检验，选 c 个质数时，如果操作得当，出错的概率仅为 \dfrac{1}{4^c}。

目前没用任何能够低于 \sqrt n 的判断质数的方法，但在 OI 界中，当 n\le 2^{78} 时，取前 12 个质数做 MR 是绝对正确的。

感觉错误概率很可以忽略了，至少对付本题取 3,7,61 足够。

然后这个题虽然 l,r\le 10^{18}，但是一个数字超过 10 位之后，由抽屉原理可得必然有数位重复。

然后对于十位数，如果没有重复数字，则必然 0,1,\cdots,9 都出现恰好一次，各数位之和为 45，显然是 3 的倍数，可以直接跳。

然后我们考虑直接爆搜所有符合条件二的数字，然后把质数存起来，也就二十多万个，排序完之后二分即可。

注意的是有点卡常，千万别 dill，然后加一点正常的卡常技巧就能 A 了。

感觉挺简单，但是我不会 T1 却秒了 T4，有点小丑。

放一个我也不知道对不对的 MR：

vector<int> P = {3, 7, 61};
I int Pow(int a, int b, int p) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = 1ll * ans * a % p;
        a = 1ll * a * a % p; b >>= 1;
    }
    return ans;
}
I bool check(int x, int p) {
    int T = ctz(x - 1);
    int now = Pow(p, x - 1 >> T, x), pre;
    if(now == 1) return 1;
    while(T--) {
        pre = now;
        now = 1ll * now * now % x;
        if(now == 1) return pre == x - 1;
    }
    return 0;
}
I bool isprime(int x) {
    if(x == 0 || x == 1) return 0;
    for(int i = 0; i < P.size(); i++) {
        if(x == P[i]) return 1;
        if(x % P[i] == 0) return 0;
        if(!check(x, P[i])) return 0;
    }
    return 1;
}