提交记录 #479096

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#479096	#249. Miller Rabin 算法	zhouzizhe^#	WA	2ms	3656kb	C++14	653b	2024-07-15 14:57:37	2024-07-15 14:57:37

Judging History

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

[2024-07-15 14:57:37]
评测

测评结果：WA
用时：2ms
内存：3656kb

查看

[2024-07-15 14:57:37]
提交

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;
    }
    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(check(i,a)==0)return 0;
        return 1;
    }
}

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

源文件, 语言: C++14

詳細信息

Test #1:

score: 0

Wrong Answer

time: 2ms

memory: 3656kb

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'

QOJ.ac

QOJ

Judging History

answer

詳細信息

Test #1:

input:

output:

result: