QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #474322 | #249. Miller Rabin 算法 | templatetemplate# | WA | 9ms | 3668kb | C++17 | 699b | 2024-07-12 17:24:23 | 2024-07-12 17:24:24 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int st[20]={2,3,5,7,11,13,17,19,23,29,31,37};
inline ll power(ll x,ll y,ll p){
ll res=1;
while(y){
if(y&1) res=res*x%p;
x=x*x%p,y>>=1;
}
return res;
}
inline bool Millar_Rabin(ll x){
if(x==1||x==4) return 0;
ll k=x-1,r=0;
while(!(k&1)) k>>=1,r++;
for(int i=0;i<12;i++){
if(x==st[i]) return 1;
if(power(st[i],x-1,x)!=1) return 0;
ll val=power(st[i],k,x);
for(int j=1;j<=r&&val!=1;j++){
ll nxt=(__int128)val*val%x;
if(val!=x-1&&nxt==1) return 0;
val=nxt;
}
}
return 1;
}
int main(){
ll n;
while(scanf("%lld",&n)!=EOF) puts(Millar_Rabin(n)?"Y":"N");
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 9ms
memory: 3668kb
input:
996581938833575363 971646509461160317 773155992127361153 161603952726515268 540879144500456953 476831214764178553 784255927154201144 671096087619405061 805545190025269709 339546334309245137 337726347922962343 222956293307015293 809183111090275843 799050063298926344 691718101820598109 646220213113313...
output:
N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N N ...
result:
wrong answer 2nd lines differ - expected: 'Y', found: 'N'