【日常學習】乘法逆元&&歐拉定理&&費馬小定理&&歐拉函數應用&&常大學霸

轉載請注明出處 [ametake版權所有]http://blog.csdn.net/ametake歡迎來看看

今天花了一個多小時終于把乘法逆元搗鼓明白了 鑒于我拙計的智商抓緊把這些記錄下來 在此本欄目鳴謝裡奧姑娘和熱心網友himdd的幫助和支援

那麼正文開始···

逆元是幹什麼的呢？

因為（a/b）mod p ≠(a mod p)/(b mod p)

我們需要想一種方法避免高精

那就是把除法轉化為乘法 因為(a*b) mod p = ( a mod p ) *( b mod p )

怎麼轉化呢？逆元出現了。

若對于數字A,C 存在X，使A * X = 1 (mod C) ,那麼稱X為 A 對C的乘法逆元。

說白了，除以一個數取模的話，和乘以這個數的逆元取模效果是一樣的。

為什麼效果一樣？讓我們來看下面的例子:

12 / 4 mod 7 = ? , 很顯然結果是3

我們現在對于數對 (4,7), 可以知道 X = 2是 4 對7的乘法逆元即2*4=1（mod 7)

那麼我們有(12 / 4) * (4 * 2 ) = (?) * (1) (mod 7)

除法被完美地轉化為了乘法

理論依據:

F / A mod C = ?

如果存在 A*X = 1 (mod C)//為什麼是1，因為上面乘法中(?) * (1) (mod 7)應該是1這個數才會不變

那麼2邊同時乘起來,得到 F * X = ? (mod C)

現在我們知道，除以一個數取模等于乘以這個數的逆元取模 接下來就是求逆元了 求逆元其實就是求使A*X = 1 (mod C)成立的X，其中A是除法中的除數

歐拉定理-費馬小定理告訴我們：如果a與p互質，則a^phi(p)=1 (mod p);特别地，當p是質數，a^(p-1)=1 (mod p) 因為此時phi(p)=p-1

由于a^phi(p)=1 (mod p) （意思是a^phi(p) mod p =1）

是以a*a^(phi(p)-1)=1 (mod p)  也就是說 對比我們可以看出X就是(phi(p)-1)

我們用X表示a的逆元 那麼它等于a的phi(p)-1次方

而我們又可以證明：當a與f互素時，a關于模f的乘法逆元有唯一解。如果不互素，則無解。如果f為素數，則從1到f-1的任意數都與f互素，即在1到f-1之間都恰好有一個關于模f的乘法逆元。

（互質唯一解不互質無解，雖然我也不明白為什麼，王若松前輩課件上也沒講明白，以後再問問吧（其實可以請教常學霸的···））

而事實上，逆元屬于群論的範疇，但鄙人的群論知識基本為0，是以遙指度受

那麼我們到底該如何求除法取模呢？b/a mod c 1.篩法求歐拉函數表O(nlogn) 2.快速幂求出每個函數的逆元O(logn)*枚舉要求的數O(n)=O(nlogn) 合計O(2nlogn)=O(nlogn)

這是用費馬小定理求 當然也可以用擴充歐幾裡得 但我還不大明白 再慢慢學

熱烈歡迎好人TY君回到XB組的窩哼(ˉ(∞)ˉ)唧

——江山代有才人出，各領風騷數百年