首页 > 代码库 > 转载 乘法逆元
转载 乘法逆元
数学公式支持不能。。只能截图
b在模m 下存在逆元的条件： b与m互质（ 即gcd（b,m） == 1 ）。
求逆元又分三种方法，拓展欧几里得法，欧拉函数法，费小马法。从一般到特殊吧：
1、拓展欧几里得法：
要求：a与m互质。
代码：
void ext_gcd(int a, int b, int &d, int &x, int &y){ if(!b) { d = a; x = 1; y = 0; } else { ext_gcd(b, a%b, d, y, x); y -= x*(a/b); }}int mod_inverse(int a, int m){ int x, y,d; ext_gcd(a, m, d, x, y); return (m + x % m) % m;}
2、欧拉函数法
要求：b与m互质。
代码：
int eurler_phi(int n){ int res = n; for(int i = 2; i * i <= n; i++){ if(n % i == 0){ res = res / i * (i - 1); while(n % i == 0) n /= i; } } if(n != 1) res = res / n * (n - 1); return res;}
3、费小马定理法
代码：可用快速幂幂
转载 乘法逆元
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。