loj #143. 质数判定

\(\color{#0066ff}{ 题目描述 }\)

判定输入的数是不是质数。

\(\color{#0066ff}{输入格式}\)

若干行，一行一个数 \(x\)。

行数不超过 \(10^5\)。

\(\color{#0066ff}{输出格式}\)

对于输入的每一行，如果 \(x\) 是质数输出一行 \(Y\)，否则输出一行 \(N\)。

\(\color{#0066ff}{输入样例}\)

1 2 6 9 666623333

\(\color{#0066ff}{输出样例}\)

N Y N N Y

\(\color{#0066ff}{数据范围与提示}\)

\(1≤x≤10^{18}\)。

\(\color{#0066ff}{ 题解 }\)

就是个Miller Rabbin的板子题

详解

#include<bits/stdc++.h> #define LL long long LL in() {char ch; LL x = 0, f = 1;while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));return x * f; } int prime[] = {2, 3, 5, 7, 11, 61, 24251}; LL msc(LL x, LL y, LL mod) {x %= mod;y %= mod;LL c = (long double)x / mod * y;LL d = x * y - c * mod;return ((d % mod) + mod) % mod; } LL ksm(LL x, LL y, LL mod) {LL re = 1LL;while(y) {if(y & 1) re = msc(re, x, mod);x = msc(x, x, mod); y >>= 1;}return (re + mod) % mod; } bool judge(LL a, LL p) {LL s = p - 1;while(!(s & 1)) s >>= 1;LL k = ksm(a, s, p);while (s != p - 1 && k != 1 && k != p - 1) k = msc(k, k, p), s <<= 1;return (k == p - 1) || ((s & 1)); } bool judge(LL n) {if(n == 1) return false;for(int i = 0; i < 7; i++) {if(n == prime[i]) return true;if(n % prime[i] == 0) return false;if(!judge(prime[i], n)) return false;}for(int i = 1; i <= 10; i++) if(!judge(2 + rand() % (n - 2), n)) return false;return true; }int main() {LL n;while(~scanf("%lld", &n)) printf(judge(n)? "Y\n" : "N\n");return 0; }

转载于:https://www.cnblogs.com/olinr/p/10305930.html

总结

以上是生活随笔为你收集整理的loj #143. 质数判定的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。