【日常学习】乘法逆元&&欧拉定理&&费马小定理&&欧拉函数应用&&常大学霸

向右看齐 2022-08-05 05:26 215阅读 0赞

今天花了一个多小时终于把乘法逆元捣鼓明白了 鉴于我拙计的智商抓紧把这些记录下来 在此本栏目鸣谢里奥姑娘和[热心网友himdd][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，因此遥指[度受][Link 1]

那么我们到底该如何求除法取模呢？b/a mod c 1.筛法求欧拉函数表O(nlogn) 2.快速幂求出每个函数的逆元O(logn)\*枚举要求的数O(n)=O(nlogn) 合计O(2nlogn)=O(nlogn)

这是用费马小定理求 当然也可以用[扩展欧几里得][Link 2] 但我还不大明白 再慢慢学

热烈欢迎好人TY君回到XB组的窝哼(ˉ(∞)ˉ)唧

——江山代有才人出，各领风骚数百年

[http_blog.csdn.net_ametake]: http://blog.csdn.net/ametake
[himdd]: http://blog.himdd.com/archives/913
[Link 1]: http://baike.baidu.com/link?url=m6PdZGPdZJGZ8s_v14GY9ywJJQOCEEWKBwbHJa5R9SvnPoJuUCat9CpFfgz9rXfVgF7fRxXp_r2V0tzmCXMmoK
[Link 2]: http://blog.himdd.com/archives/640