广西网络干部学院,郑州百度seo网站优化,网站建设案例赏析,重庆市建设工程造价信息2020什么是乘法逆元#xff1f;
算数意义上的乘法逆元指的是倒数#xff0c;即#xff1a;a*#xff08;1/a#xff09;1
所以 1/a 是 a在算数意义下的乘法逆元#xff0c;或者可以说二者互为逆元。 这有什么用呢#xff1f;
除以a就等于乘上a的乘法逆元#xff0c;乘以…什么是乘法逆元
算数意义上的乘法逆元指的是倒数即a*1/a1
所以 1/a 是 a在算数意义下的乘法逆元或者可以说二者互为逆元。 这有什么用呢
除以a就等于乘上a的乘法逆元乘以a等于除以a的乘法逆元。 那么我们回到我们要介绍的新的乘法逆元模意义上的乘法逆元。(使用条件当一个正整数做分母的时候
例如我们要求xy*x-y/2 mod p
很显然对于分子我们可以直接用模的性质 xy*x-ymodp 【xy%p *x-y)%p】%p
但是这样的方法只对加减乘有效。 除法的话由于整除向下取整的原因我们无法直接使用。这时候就要用到逆元来代替除法因为除以一个数取模等于乘上它在模意义上的逆元后取模。
ok那么什么是模意义上的乘法逆元呢 给出定义 a*x 1modp也就是a*x对p取模为1的时候x就是a 的逆元所以当除以a的时候就相当于是乘上a的逆元x。注意模只对整数时有意义的所以我们的变量都应该是整数
那么我们知道了模意义上的乘法逆元应该怎么求它的乘法逆元呢 就可以用到三种方法扩展欧几里得算法费马小定理线性递推。 扩展欧几里得算法 a*x1 modp 这个式子可以展开写成扩展欧几里得相关文章连接《洛谷深入浅出进阶篇》 欧几里得算法裴蜀定理拓展欧几里得算法————洛谷P1516 青蛙的约会-CSDN博客https://blog.csdn.net/louisdlee/article/details/134751119?spm1001.2014.3001.5502 a*xp*y1 也就是求xy的不定方程。 我们由裴蜀定理可知这个方程只有gcdap1的时候才有解所以gcd1是求逆元的前提条件。 然后我们直接套exgcdapxy即可 虽然求出来的是a的一个逆元但是我们由拓展欧几里得可以求出通式xx1k*lcmap/a k可以取任意整数 只要不断模数p就可以求出最小正整数解 2费马小定理如果p是质数且gcdap1a^(p-2)是a的一个乘法逆元。 那么如何求a^(p-2)? 我们可以用到快速幂的方法 s1tp-2 ya whilet0{ ifp11ss*y y*y t/2; } 线性递推求逆元
假如给你1~n个数让你求所有整数在模p意义下的乘法逆元。你应该怎么办n1e6)
如果你每次都用exgcd或者费马小定理快速幂这题是肯定是会超时的所以我们只能用线性优化了。
只能使用递推的方式来解决这道题
那么我们必须找到递推的式子
假设 invi是i在模意义下的逆元记住板子即可
设pi*qr其中q【p/i】整除rp%i。 第一个式子pi*qr
在模意义下可以得到这样的式子 i*qr 0 mod p
变形为 i -r/q mod p
等价于i -r * invq mod p
两边取倒数整数的倒数来表示逆元函数
1/i -1/r * q
invi -invr*q -invr*【p/i】
因为 rp%i所以r是一定小于当前的i的怎么求invr
由于我们是递推求逆元当求到i时说明i-1i-2,......1 都求出来了。
所以我们只要注意边界 inv1 1即可
但是还是有一个问题就是这样求出来的逆元有些是负数的如果我们要求逆元的最小正整数应该怎么办 那也好办不断在其后面加上p就可以了当逆元大于0退出循环。 上代码
#define _CRT_SECURE_NO_WARNINGS
#includeiostream
#includecstdio
#includecmath
#includestring
#includecstring
#includestring
#includealgorithm
#includevector
#includecctype
#includemap
#includeset
#includequeue
#includenumeric
#includeiomanip
using namespace std;
typedef long long LL;
const int N 3e6 7;
LL inv[N];
int main()
{LL n,p;cin np;inv[1] 1;for (int i 2; i n; i) {LL q p / i;LL r p % i;inv[i] (-q * inv[r]%p)%p;while(inv[i]0)inv[i]p;}for (int i 1; i n; i)cout inv[i] \n;
}
