國立新竹科學園區實驗高級中學 H10335廖丞胤數學科學習歷程檔案:費馬小定理與模反元素

# 國立新竹科學園區實驗高級中學 H10335廖丞胤數學科學習歷程檔案:費馬小定理與模反元素 ## 前言某天的下午我正坐在座位上寫著競賽程式的題目，我的一位朋友(我們暫且稱他為$P_L$)$P_L$傳了一個有趣的題目給我，是跟排列組合有關的，題目的詳細我也忘了，就在我花了半個小時想出解法後，我卡在一個瓶頸:執行時限。競賽程式對於執行時間的限制十分嚴謹，有時不用特定的演算法而單用暴力搜尋，執行的結果往往會是`TLE`(Time Limit Exceeded,執行時間超時的意思)，而在那個題目限制住我的瓶頸就是求$C^n_k$的速度不夠快($1\le n,k\le10^5$，因為這個數字出來的$(^n_k)$會超大，所以題目要求要先模$10^9+7$:這是一個質數)。後來問了$P_L$到底是怎麼解出來的?會不會是我多想了甚麼導致沒有看到優化的捷徑，他給我看他的程式碼，構想跟我的完全一樣，只差在求$C^n_k$的部分，他用了$O(n\cdot logMod)$就預處理完$C^n_k$的部分，他只要每次花$O(1)$就可以查詢出來，完全海放我的$O(nk)$，他解釋的時候講到了兩個聽起來很難的東西: 費馬小定理跟模反元素。 ## 費馬小定理 "假設a,p皆為整數，且p為質數，則式(1)必成立" $a^p\equiv a\pmod p$ 式(1) "又若a不是p的倍數，則可以將式(1)改寫為式(2)" $a^{p-1}\equiv 1\pmod p$ 式(2) ### 證明: 考慮 $(^p_n)=\frac{p!}{n!(p-n)!}$且限定$n$不為$p$或$0$，則分子有質數$p$，但分母不含$p$，故分子的$p$必定會被保留不被除去，即$(^p_n)$恆為$p$的倍數。再考慮$(b+1)^{p}$的展開模$p$，得: $(b+1)^p\equiv (^p_p)b^p+(^p_{p-1})b^{p-1}+(^p_{p-2})b^{p-2}+\dots+ (^p_{1})b^{1}+(^p_0)b^0\pmod p$ $\equiv(^p_p)b^p+(^p_0)b^0\pmod p$ $\equiv b^p+1\pmod p$ 因此 $(b+1)^p \equiv b^p+1\pmod p$ $\equiv (b-1)^p+1+1\pmod p$ $\equiv (b-2)^p+1+1+1\pmod p$ $\dots$ $\equiv 1+1+1+1+1\dots+1\pmod p$ (共$b+1$個) $\equiv b+1\pmod p$ 令$b=a-1$，即得$a^p\equiv a\pmod p$ 證畢$\#$ ## 模反元素一整數$a$對模$n$的模反元素為$b$，則式(3)成立 $a^{-1}\equiv b\pmod n$ 式(3) 也可整理為 $ab\equiv 1 \pmod n$ 這個$b$存在的充分必要條件是$a,n$戶質若$b$存在，**在模數$n$的除法下可以用和對應的模反元素的乘法來達成** ### 求模反元素根據費馬小定理$a^p\equiv a\pmod p$，如果$p$為質數，則可以改寫為$a^{p-1}\equiv 1\pmod p$，$a^{p-1} \equiv a \cdot a^{p-2}\equiv 1 \pmod p$，$a$模$p$的模反元素即為$a^{p-2}$ ## 關於$O(NlogMod)$求$C^n_k$的實現 > 明明就可以直接線性求階乘然後直接代公式啊?用這個幹嘛? 我們都知道這個方式在$n,k$很小的時候是可以運作的，但你要考慮到: ### 題目要求我們模$10^9+7$ 就算我們先算出階乘，乘出$C^n_k$後再模，也會因為$overflow(溢位)$造成錯誤 "C++ `unsigned long long`範圍:$0 \sim 2^{64}-1$，就算開這個也存不下$(10^5)!$" ### C++的實現我們就是先$O(N)$算出$1\sim n$的所有的階乘，然後每次求出$i!$的時候花$O(logMod)$求出模反元素，之後查詢只要花$O(1)$這樣算 $n!\times rev(k!)\times rev((n-k)!)\pmod {Mod}$ ($x$的模反元素表示為$rev(x)$) 這樣我們就達成$O(N\cdot logMod)$求$C^n_k$ ```cpp= #include <bits/stdc++.h> #define int long long #define MOD Mod1 using namespace std; const int Mod1=1000000007; int factorial[200005],rev[200005]; int po(int xx,int yy){//矩陣快速冪，競賽的另一個技巧，下次有機會我們再來深入討論 if(yy==0)return 1; if(yy==1)return xx; int zz=po(xx,yy/2); int ww=(zz*zz)%MOD; if(yy%2==1)return (ww*xx)%MOD; return ww; } void precalculate(){ factorial[0]=factorial[1]=rev[0]=rev[1]=1;//factorial[i]存i!模MOD for(int i=2;i<100005;i++){ //rev[i]存factorial[i]模MOD的模反元素 factorial[i]=factorial[i-1]*i%MOD; rev[i]=po(factorial[i],MOD-2); } } int cmod(int a,int b){ return factorial[a]*rev[b]%MOD*rev[a-b]%MOD; } signed main(){ precalculate(); int n,k;cin>>n>>k; cout<<cmod(n,k)<<endl; }//基本上這個程式就是輸入n,k然後輸出Cn取k模10^9+7 ``` ## 後續與結語當下我改完求$C^n_k$的部分後上傳就順利拿到滿分了，我真的是很佩服$P_L$，感覺他總是能找到神奇的數學性質並且運用在競賽上。所以為了不輸給他太多，在學完這個後我又上網研究了一些其他經典的數學理論，並且發現許多曾經在競賽時看到的題目，或是一些可以運用在競賽上的技巧，這讓我更加的對數學有興趣，研究這些理論讓我覺得蠻快樂的，未來我還會不斷探索之前從未學習過的東西，希望能夠有更多有趣的收穫。