大型 网站的建设 阶段,个人网站需不需要搭建服务器,新闻资讯专业翻译公司,wordpress商城 微信支付宝Miller-Rabin素数测试 给出一个小于1e18的数#xff0c;问它是否为质数#xff1f;不超过50组询问。hihocoder 我是真的菜#xff0c;为了不误导他人#xff0c;本篇仅供个人使用。 首先#xff0c;一个1e18的数#xff0c;朴素\(O(\sqrt{n})\)素数判定肯定爆炸。怎么办呢…Miller-Rabin素数测试 给出一个小于1e18的数问它是否为质数不超过50组询问。hihocoder 我是真的菜为了不误导他人本篇仅供个人使用。 首先一个1e18的数朴素\(O(\sqrt{n})\)素数判定肯定爆炸。怎么办呢 我们知道对于素数p只要a不是p的倍数一定有\(a^{p-1}1\mod p\)。那么我们是不是可以选出某些a对于要判定的数p看看他是否满足以a为底的费马小定理以此来判定质数呢答案是基本可以。 但是很不巧有一类合数以任何小于它们的质数为底进行判定结果都是正确的。它们叫做伪素数。怎么排除伪素数的情况呢有个叫做二次探测定理的东西若\(x^21\mod p\)那么\(或x1或-1\mod p\)。 假设\(a^{x-1}1\mod p\)成立。如果x-1为奇数就不再判定下去。否则根据二次探测定理还可以继续去判定\(或a^{\frac{x-1}{2}}1或-1\mod p\)是否成立。如果它不等于1或-1就返回false。如果它等于-1就返回true。如果它等于1就继续判定下去。反正只要x-1为偶数并且\(a^{x-1}1\mod p\)就可以一直判定。这样就可以把那些伪素数排除掉了。这就叫做miller-rabin素数测试。据说选前7个质数作为a在1e18内也只有两三个会被miller-rabin判定成素数的合数。 #include cstdio
using namespace std;typedef long long LL;
const LL m7, a[m]{2, 3, 5, 7, 11, 13, 17};
LL n, p;LL fmul(LL a, LL b, LL p){ //将b分解为二进制返回a*b%pLL ans0;for (; b; b1, aa, a%p)if (b1) ansa, ans%p;return ans;
}LL fpow(LL a, LL x, LL p){LL ans1, basea;for (; x; x1, basefmul(base, base, p))if (x1) ansfmul(ans, base, p);return ans;
}bool MR(LL a, LL x, LL p){ //判断是否a^x1或p-1 (mod p)且mr下去也成立LL tfpow(a, x, p);if (t!1t!p-1) return false;if (t1x1||tp-1) return true;return MR(a, x1, p);
}bool isprime(LL p){if (p10) return false;for (LL i0; im; i){if (pa[i]) return true; //互质时费马小定理才成立if (fpow(a[i], p-1, p)!1) return false;if (!MR(a[i], (p-1)1, p)) return false;}return true;
}int main(){scanf(%lld, n);while (n--){scanf(%lld, p);puts(isprime(p)?Yes:No);}return 0;
} 转载于:https://www.cnblogs.com/MyNameIsPc/p/9314006.html
