這題可以用米勒-拉賓(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;
}
這題可以用米勒-拉賓(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;
}
電~~~~~~
這題可以用米勒-拉賓(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;
}
電~~~~~~
\電神教我写程式~~~/
nick930212@gmail.com
(arod571431)
學校
:
國立臺北科技大學
編號 : 119219
來源 : [49.159.218.30]
最後登入時間 ：
2023-07-25 15:13: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;
}
電~~~~~
電