發表新討論
#23318: 米勒-拉賓(MillerRabbin)演算法(C++)


DE45A (一葉之秋)

f394. 心愛數質數 | From: [1.172.150.32] | 發表日期: 2020-11-07 17:49

 

這題可以用米勒-拉賓(MillerRabbin)演算法

附上關鍵程式碼(注意益位問題)

bool M_R(long long a,long long n){

long long d=n-1,r=0;

while(d%2==0)d/=2,++r;

long long k=pow(a,d)%n;

if(k==1)return true;

for(int i=0;i<=r;++i,k=k*k%n){

if(k==n-1)return true;

}

return false;

}

#23350: Re:米勒-拉賓(MillerRabbin)演算法(C++)


HaKkaz (luckyanthonyan)

f394. 心愛數質數 | From: [203.64.161.234] | 發表日期: 2020-11-09 16:18

 

這題可以用米勒-拉賓(MillerRabbin)演算法

附上關鍵程式碼(注意益位問題)

bool M_R(long long a,long long n){

long long d=n-1,r=0;

while(d%2==0)d/=2,++r;

long long k=pow(a,d)%n;

if(k==1)return true;

for(int i=0;i<=r;++i,k=k*k%n){

if(k==n-1)return true;

}

return false;

}


電~~~~~~

#23351: Re:米勒-拉賓(MillerRabbin)演算法(C++)


valder (valder)

f394. 心愛數質數 | From: [203.64.161.163] | 發表日期: 2020-11-09 16:19

 

這題可以用米勒-拉賓(MillerRabbin)演算法

附上關鍵程式碼(注意益位問題)

bool M_R(long long a,long long n){

long long d=n-1,r=0;

while(d%2==0)d/=2,++r;

long long k=pow(a,d)%n;

if(k==1)return true;

for(int i=0;i<=r;++i,k=k*k%n){

if(k==n-1)return true;

}

return false;

}


電~~~~~~


\電神教我写程式~~~/

#23484: Re:米勒-拉賓(MillerRabbin)演算法(C++)


nick930212@gmail.com (arod571431)

f394. 心愛數質數 | From: [114.136.123.116] | 發表日期: 2020-11-21 19:28

 

這題可以用米勒-拉賓(MillerRabbin)演算法

附上關鍵程式碼(注意益位問題)

bool M_R(long long a,long long n){

long long d=n-1,r=0;

while(d%2==0)d/=2,++r;

long long k=pow(a,d)%n;

if(k==1)return true;

for(int i=0;i<=r;++i,k=k*k%n){

if(k==n-1)return true;

}

return false;

}


電~~~~~

電

ZeroJudge Forum