QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#479147	#249. Miller Rabin 算法	zhouzizhe^#	WA	82ms	3960kb	C++14	679b	2024-07-15 15:24:19	2024-07-15 15:24:19

Judging History

你现在查看的是最新测评结果

[2024-07-15 15:24:19]
评测

测评结果：WA
用时：82ms
内存：3960kb

查看

[2024-07-15 15:24:19]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long

vector<ll> P={2,3,5,7,11,13,17,19,23,29,31,37};

bool check(ll p,ll n){
    ll b=n-1,ret=1;
    while(b){
        if(b&1)ret=__int128(ret)*p%n;
        ll a=p;
        p=__int128(p)*p%n;
        if(p==1 && a!=n-1 && a!=1)return 0;
        b>>=1;
    }
    if(ret!=1)return 0;
    return 1;
}


ll MillerRabin(ll a){
    if(a<=40){
        for(ll i:P)if(i==a)return 1;
        return 0;
    }
    else{
        for(ll i:P)if(a%i==0 || check(i,a)==0)return 0;
        return 1;
    }
}

int main(){
    ll a;
    while(scanf("%lld",&a)!=-1)printf("%c\n",MillerRabin(a)?'Y':'N');
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 82ms

memory: 3960kb

input:

996581938833575363
971646509461160317
773155992127361153
161603952726515268
540879144500456953
476831214764178553
784255927154201144
671096087619405061
805545190025269709
339546334309245137
337726347922962343
222956293307015293
809183111090275843
799050063298926344
691718101820598109
646220213113313...

output:

N
Y
Y
N
Y
Y
N
Y
Y
Y
Y
Y
Y
N
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
...

result:

ok 15000 lines

Test #2:

score: 0

Accepted

time: 50ms

memory: 3772kb

input:

292094793288448159
456918231632780153
52701684901220791
755430520029564023
202037556396478813
224321375550698537
953758266735232253
68668310674613297
730895589897264853
344428227893888993
521429852982590257
547788290718839273
332181270020381261
876010276438312333
906474115171090099
26200832832269134...

output:

N
N
Y
N
N
N
Y
N
Y
N
N
N
N
N
Y
N
Y
N
Y
Y
N
Y
Y
N
Y
N
Y
N
Y
N
Y
N
N
Y
N
Y
Y
Y
N
N
Y
N
Y
Y
Y
N
N
N
Y
N
N
Y
Y
N
N
N
N
Y
N
N
N
N
N
Y
Y
N
N
N
N
N
Y
N
Y
Y
Y
N
N
Y
N
Y
N
Y
N
N
Y
Y
N
N
N
N
Y
Y
N
Y
N
N
N
N
Y
Y
Y
N
Y
N
N
Y
N
N
Y
Y
Y
Y
Y
Y
Y
N
Y
N
N
N
Y
N
N
N
Y
N
Y
N
N
Y
N
N
N
Y
Y
Y
N
Y
Y
Y
N
Y
N
N
N
Y
N
Y
N
Y
...

result:

ok 15000 lines

Test #3:

score: -100

Wrong Answer

time: 76ms

memory: 3752kb

input:

37686301288201
83818601792630641
73103085605161
146313732835525609
228087610722516540
343255869017446321
132173451449926849
461798530935794823
171613522570639321
746139393134794441
700705956080852569
186402586980996590
116687280644971921
439801455648601
608187424599317161
582838391995869241
29815648...

output:

Y
Y
Y
Y
N
Y
Y
N
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
N
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
N
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
Y
Y
Y
Y
Y
Y
Y
N
Y
Y
N
...

result:

wrong answer 1st lines differ - expected: 'N', found: 'Y'