正題

題目鏈接:https://loj.ac/p/143

---

題目大意

給出一個數$p$，讓你判定是否為質數。

---

解題思路

$Miller?Rabin$是一種基于費馬小定理和二次探測定理的具有較高正確性的高效質數判定算法。
首先講一下兩個定理

費馬小定理：$$gcd(a,p)=1?a^{p?1}=1(modp)$$

二次探測定理：若$p$是一個素數且有$0<x<p$那么有$$x^n=1(modp)?n=1orp?1$$

這兩個定理我們怎么使用呢，我們先將$p?1$分解成$2^{s}t$的形式，這樣我們對于一個數$a^t$就可以進行$s$次平方將其變為$a^{p?1}$。

再選取一個較小的質數$a$，然后不停將$a^t$平方，每平方一次就使用一次二次探測定理來判定質數。知道$a^t$平方$s$次后變為$a^{p?1}$就再用一次費馬小定理。

當然這樣無法完全保證正確性，但是如果我們多拿幾個質數試一試就可以大大縮小錯誤概率。并且目前可以證明在$int$范圍內使用前$30$個質數是保證不會出錯的，但是一般代碼中為了確保效率會使用少一些素數。

注意使用$longlong$時乘數可能會超過范圍，所以可以用黑科技$O(1)$的快速乘來解決

---

code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll pri[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71}; ll ksc(ll a,ll b,ll p){a%=p;b%=p;ll c=(long double)a*b/p;long double ans=a*b-c*p;if(ans<0)ans+=p;else if(ans>=p)ans-=p;return ans; } ll power(ll x,ll b,ll p){ll ans=1;while(b){if(b&1)ans=ksc(ans,x,p);x=ksc(x,x,p);b>>=1;}return ans; } bool Mr(ll p){if(p==2)return 1;if(p<2||!(p&1))return 0;ll s=0,t=p-1;while(!(t&1))s++,t>>=1;for(ll i=0;i<10&&pri[i]<p;i++){ll x=power(pri[i],t,p),k;for(ll j=0;j<s;j++){k=ksc(x,x,p);if(k==1&&x!=1&&x!=p-1)return 0;x=k;}if(x!=1)return 0;}return 1; } int main() {ll x;while(scanf("%lld",&x)!=EOF){if(Mr(x))printf("Y\n");else printf("N\n");} }

總結

以上是生活随笔為你收集整理的Loj#143-[模板]质数判定【Miller-Rabin】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。