企业介绍微网站怎么做的,手机软件商城免费下载,建设专业网站哪家更专业,lamp环境做网站目录
逆元
加法逆元
乘法逆元
如何求
快速幂
扩展欧几里得
O(n)求1到n的乘法逆元 逆元
数学中#xff0c;逆元素#xff08;英语#xff1a;Inverse element#xff09;推广了加法中的加法逆元和乘法中的倒数。直观地说#xff0c;它是一个可以取消另一给定元素运…目录
逆元
加法逆元
乘法逆元
如何求
快速幂
扩展欧几里得
O(n)求1到n的乘法逆元 逆元
数学中逆元素英语Inverse element推广了加法中的加法逆元和乘法中的倒数。直观地说它是一个可以取消另一给定元素运算的元素。
加法逆元
对于一个任意数n存在加法逆元英语Additive Inverse又称相反数其与nn的和为零加法单位元。n的加法逆元表示为-n。
乘法逆元
数学上一个数xx的倒数reciprocal或称乘法逆元multiplicative inverse是指一个与x相乘的积为1的数。显然在实数范围内x的乘法逆元是1/x。
信息学中常用的乘法逆元是模逆元。 一整数a对同余n之模逆元是指满足以下公式的整数b a b ≡ 1 (mod n). 整数a对模数n之模逆元存在的充分必要条件是a和n互素若此模逆元存在在模数n 下的除法可以用和对应模逆元的乘法来达成此概念和实数除法的概念相同。
如何求
快速幂
对于质数pp考虑费马小定理a^(p−1) mod p 1可以得到ii的逆元是pow(i, p - 2, p)。
对于合数pp考虑欧拉定理a^(φ(p) ) mod p 1可以得到ii的逆元是pow(i, phi(p) - 1, p)。 但是因为对于一般的数字计算φ(p)复杂度较高并不使用这个方法。
扩展欧几里得
因为快速幂非常好写一般只有在模非质数或者是卡常数的情况下使用这个算法。 解出axpy1的一组解(x,y)x就是a关于模n的其中一个模逆元。 需要注意求解出的xx可能是负数。
O(n)求1到n的乘法逆元
inv[1] 1;
for (int i 2; i n; i) {inv[i] (long long)inv[p % i] * (p - p / i) % p;
}这个方法可以用于组合数的预处理。
这个方法还可以改写为递归版以替代质数情况下用快速幂求逆元。
int inv(int x) {if (x 1) {return 1;} else {return (long long)inv(p % i) * (p - p / i) % p;}
}另一个常用与组合数预处理的做法是 先预处理出1到n的阶乘然后计算n阶乘的逆元然后倒序推出n到1阶乘的逆元。
fac[0] 1;
for (int i 1; i n; i) {fac[i] (long long)fac[i - 1] * i % p;
}
invfac[n] pow(fac[n], p - 2, p);
for (int i n - 1; i 0; i--) {invfac[i] (long long)invfac[i 1] * (i 1) % p;
}
