自动搬运

查看原文

来自洛谷，原作者为

	zzx0102 原 sto_5k_orz || AFO on 2023.10.21

搬运于2025-08-24 22:57:39，当前版本为作者最后更新于2024-05-03 15:49:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：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;
}