数学 |
您所在的位置：网站首页 › 离散数学求逆元的简便方法有哪些呢 › 数学 |
数学
|
本文参考文献：《算法竞赛从入门到进阶》 作者：罗勇军 再次感谢罗老师的支持 同余在数论中非常实用，它用类似处理等式的方式来整除关系，非常简便。 1.同余 两个整数a,b和一个正整数m，如果 a 除以 m 所得的余数 和 b除以m所得的余数相等，即 a mod m =b mod m,称为 a和 b对于m同余，m称为同余的模。 同余的符号记为 a ≡ b( mod m)。2.一元线性同余方程（同余：顾名思义余数相同） ax ≡ b（ mod m） 理解：即 ax 除以 m, b 除以 m,两者余数相同，这里 a、b、m都是整数，求解x的值。3.逆元 给出 a 和 m,求解方程 ax ≡ 1( mod m),即 ax 除以m余数是 1。 方程 ax ≡ 1( mod m)的一个解 x，称 x 为 a 的模 m 的逆。注意，这样的 x 有很多，把它们都称为逆。 求逆元的代码如下： void extend_gcd(int a, int b, int &x, int &y){ if(b == 0){ x=1,y=0; return; } extend_gcd(b, a%b, x, y); int tmp=x; x =y; y = tmp - (a /b)*y; } int mod_inverse(int a, int m){ int x, y; extend_gcd( a ,m ,x ,y); return (m + x % m) % m ;//x可能是负数，需要处理 }4. 逆元与除法取模 逆元的一个重要应用是求除法的模。 这里想起了Catalan 数，有一个需求：求（a /b）mod m,即 a除以 b，然后对 m取模。这里 a 和 b 都是很大的数，做除法后再取模会损失精度 。 如何避免损失精度呢? 方法：这里是引用 数学中 ，逆元素（英语：Inverse element）推广了加法中的加法逆元和乘法中的倒数。直观地说，它是一个可以取消另一给定元素运算的元素。 设 b 的逆元是 k，有：(这里 bk=1) （a ÷ b）mod m =((a ÷ b) mod m) ((bk ) mod m) = (a ÷ b ×bk) mod m 上述推导过程把除法的模运算转化成了乘法模运算 ：（a/b）mod m =(ak) mod m 5. 逆元与求解二元一次方程 ax + my = b 如果得到了 a 的逆，可以来求解形如 **ax ≡ b（mod m）**的任何同余方程。方法如下： 令 a′ 是 a 模 m 的逆，则 a′ a ≡ 1（mod m）；在 ax ≡ b（mod m）的两边同时乘以 a ′，得到 a′ax ≡ a′b（mod m），所以 x ≡ a′b（mod m）。 例如求 8x ≡ 24（mod 31）的解先求 8 模31 的逆，是4；然后在 8x ≡ 24（mod 31）的两边乘以4，得到 8×4x ≡ 24（mod 31），所以 x ≡ 96（mod 31）。 扩展欧几里得算法时曾求解了二元一次方程 解法： |
【本文地址】
今日新闻 |
推荐新闻 |