2 条题解
-
0
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef __int128 i128; i128 base[]={2,3,5,7,11,13,17,19,23,29,31,37}; i128 qpow(i128 a, LL b, i128 p) { i128 res=1; for(;b;b>>=1) { if(b&1) res=res*a%p; a=a*a%p; } return res; } bool Miller_Rabin(LL n) { if(n<3 || n%2==0) return n==2; LL u=n-1,k=0; while(!(u&1)) u/=2,k++; for(auto a:base) { a=a%n;if(a==0) continue; i128 v=qpow(a,u,n); if(v==1) continue; for(LL j=1;j<=k;j++) { if(v==n-1)break; v=v*v%n; } if(v!=n-1) return false; } return true; } int main() { LL n; while(scanf("%lld",&n)!=EOF) { if(Miller_Rabin(n)) printf("Y\n"); else printf("N\n"); } return 0; } -
0
huangzheng
LV 6
@ 2025-10-8 16:49:27
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef __int128 i128; i128 base[]={2,3,5,7,11,13,17,19,23,29,31,37}; i128 qpow(i128 a,LL b,i128 p) { i128 res=1; for(;b;b>>=1) { if(b&1) res=res*a%p; a=a*a%p; } return res; } bool Miller_Rabin(LL n) { if(n<3 || n%2==0) return n==2; LL u=n-1,k=0; while(!(u&1)) u/=2,k++; for(auto a:base) { a=a%n;if(a==0) continue; i128 v=qpow(a,u,n); if(v==1) continue; for(LL j=1;j<=k;j++) { if(v==n-1)break; v=v*v%n; } if(v!=n-1) return False; } return True; } int main() { LL n; while(scanf("%lld",&n)!=EOF) { if(Miller_Rabin(n)) printf("Y\n"); else printf("N\n"); } return 0; }
- 1