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


DE45A (一葉之秋)

學校 : 新北市立板橋高級中學
編號 : 68688
來源 : [1.172.131.91]
最後登入時間 ：
2024-10-12 13:01:19
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)

學校 : 國立交通大學
編號 : 83096
來源 : [203.64.161.123]
最後登入時間 ：
2024-11-08 20:42:17
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)

學校 : 新北市立板橋高級中學
編號 : 83342
來源 : [111.243.0.222]
最後登入時間 ：
2024-11-22 00:01:09
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)

學校 : 國立臺北科技大學
編號 : 119219
來源 : [49.159.218.30]
最後登入時間 ：
2023-07-25 15:13:19
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