31552人阅读
数论（68）
今天我们来探讨逆元在ACM-ICPC竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。
对于正整数和，如果有，那么把这个同余方程中的最小正整数解叫做模的逆元。
逆元一般用扩展欧几里得算法来求得，如果为素数，那么还可以根据费马小定理得到逆元为。
推导过程如下
&&&&&&&&&&&&&&&&&&&&&&&&& &&
求现在来看一个逆元最常见问题，求如下表达式的值（已知）
&&&&&&&&&&&
当然这个经典的问题有很多方法，最常见的就是扩展欧几里得，如果是素数，还可以用费马小定理。
但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的，它们都会要求与互素。实际上我们还有一
种通用的求逆元方法，适合所有情况。公式如下
现在我们来证明它，已知，证明步骤如下
接下来来实战一下，看几个关于逆元的题目。
题意：给定两个正整数和，求的所有因子和对9901取余后的值。
分析：很容易知道，先把分解得到，那么得到，那么
&&&& 的所有因子和的表达式如下
所以我们有两种做法。第一种做法是二分求等比数列之和。
#include &iostream&
#include &string.h&
#include &stdio.h&
typedef long long LL;
const int N = 10005;
const int MOD = 9901;
bool prime[N];
void isprime()
memset(prime,true,sizeof(prime));
for(int i=2; i&N; i++)
if(prime[i])
p[cnt++] =
for(int j=i+i; j&N; j+=i)
prime[j] =
LL power(LL a,LL b)
LL ans = 1;
ans = ans * a % MOD;
a = a * a % MOD;
LL sum(LL a,LL n)
if(n == 0) return 1;
LL t = sum(a,(n-1)/2);
LL cur = power(a,(n+1)/2);
t = (t + t % MOD * cur % MOD) % MOD;
LL cur = power(a,(n+1)/2);
t = (t + t % MOD * cur % MOD) % MOD;
t = (t + power(a,n)) % MOD;
void Solve(LL A,LL B)
LL ans = 1;
for(int i=0; p[i]*p[i] &= A; i++)
if(A % p[i] == 0)
int num = 0;
while(A % p[i] == 0)
A /= p[i];
ans *= sum(p[i],num*B) % MOD;
ans %= MOD;
ans *= sum(A,B) % MOD;
ans %= MOD;
cout&&ans&&
int main()
isprime();
while(cin&&A&&B)
Solve(A,B);
第二种方法就是用等比数列求和公式，但是要用逆元。用如下公式即可
&&&&&&&&&&&&&&&&&&&&&
因为可能会很大，超过int范围，所以在快速幂时要二分乘法。
#include &iostream&
#include &string.h&
#include &stdio.h&
typedef long long LL;
const int N = 10005;
const int MOD = 9901;
bool prime[N];
void isprime()
memset(prime,true,sizeof(prime));
for(int i=2; i&N; i++)
if(prime[i])
p[cnt++] =
for(int j=i+i; j&N; j+=i)
prime[j] =
LL multi(LL a,LL b,LL m)
LL ans = 0;
ans = (ans + a) %
a = (a + a) %
LL quick_mod(LL a,LL b,LL m)
LL ans = 1;
ans = multi(ans,a,m);
a = multi(a,a,m);
void Solve(LL A,LL B)
LL ans = 1;
for(int i=0; p[i]*p[i] &= A; i++)
if(A % p[i] == 0)
int num = 0;
while(A % p[i] == 0)
A /= p[i];
LL M = (p[i] - 1) * MOD;
ans *= (quick_mod(p[i],num*B+1,M) + M - 1) / (p[i] - 1);
ans %= MOD;
LL M = MOD * (A - 1);
ans *= (quick_mod(A,B+1,M) + M - 1) / (A - 1);
ans %= MOD;
cout&&ans&&
int main()
isprime();
while(cin&&A&&B)
Solve(A,B);
其实有些题需要用到模的所有逆元，这里为奇质数。那么如果用快速幂求时间复杂度为，
如果对于一个1000000级别的素数，这样做的时间复杂度是很高了。实际上有的算法，有一个递推式如下
&&&&&&&&&&&&&&&&&&
它的推导过程如下，设，那么
对上式两边同时除，进一步得到
再把和替换掉，最终得到
初始化，这样就可以通过递推法求出模奇素数的所有逆元了。
另外模的所有逆元值对应中所有的数，比如，那么对应的逆元是。
题意：求中互质的数的个数，其中。
分析：因为，所以，我们很容易知道如下结论
&&&& 对于两个正整数和，如果是的倍数，那么中与互素的数的个数为
&&&& 本结论是很好证明的，因为中与互素的个数为，又知道，所以
&&&& 结论成立。那么对于本题，答案就是
&&&&& 其中为小于等于的所有素数，先筛选出来即可。由于最终答案对一个质数取模，所以要用逆元，这里
&&&&& 求逆元就有技巧了，用刚刚介绍的递推法预处理，否则会TLE的。
#include &iostream&
#include &string.h&
#include &stdio.h&
#include &bitset&
typedef long long LL;
const int N = ;
void isprime()
prime.set();
for(int i=2; i&N; i++)
if(prime[i])
for(int j=i+i; j&N; j+=i)
prime[j] =
LL ans1[N],ans2[N];
LL inv[N];
int main()
isprime();
int MOD,m,n,T;
scanf(&%d%d&,&T,&MOD);
ans1[0] = 1;
for(int i=1; i&N; i++)
ans1[i] = ans1[i-1] * i % MOD;
inv[1] = 1;
for(int i=2;i&N;i++)
if(i &= MOD)
inv[i] = (MOD - MOD / i) * inv[MOD % i] % MOD;
ans2[1] = 1;
for(int i=2; i&N; i++)
if(prime[i])
ans2[i] = ans2[i-1] * (i - 1) % MOD;
ans2[i] = ans2[i] * inv[i % MOD] % MOD;
ans2[i] = ans2[i-1];
while(T--)
scanf(&%d%d&,&n,&m);
LL ans = ans1[n] * ans2[m] % MOD;
printf(&%lld\n&,ans);
接下来还有一个关于逆元的有意思的题目，描述如下
&&&& 所以只需要证明，而我们知道模的逆元对应全部
&&&& 中的所有数，既是单射也是满射。
&&&& 所以进一步得到
&&&&& 证明完毕！
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：2183772次
积分：23288
积分：23288
排名：第300名
原创：478篇
转载：42篇
评论：474条
(1)(4)(3)(4)(38)(4)(1)(2)(5)(1)(4)(2)(1)(7)(10)(8)(8)(12)(16)(31)(20)(28)(49)(27)(16)(42)(18)(29)(26)(15)(3)(8)(9)(8)(11)(3)(46)
(window.slotbydup = window.slotbydup || []).push({
id: '4740881',
container: s,
size: '200,200',
display: 'inlay-fix'扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
乘法逆元是什么,怎么求呢?比如说
求乘法逆远,
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
乘法群中的逆元吗?首先1是单位元的逆元是1/
为您推荐：
其他类似问题
我的百度知道玩的不熟，不太明白为什么会收到你的提问。
我也不懂，不过我们可以研究研究。。。我查过看到说乘法逆元怎么是X关于Y的乘法逆元呢。。。问题是怎么问的啊。。。
扫描下载二维码【图文】辗转相除法求模的逆元_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
辗转相除法求模的逆元
大小：405.50KB
登录百度文库，专享文档复制特权，财富值每天免费拿！
你可能喜欢在MOD的情况下， &（a*b/c ) %MOD &不能直接 / c 来求，需要找到一个数 inv 使得 &inv * c % MOD = 1 。 这样 (a*b / c) % MOD &= (a * b * inv) % MOD;
性质： 逆元是积性函数 & 存在 &a*b = c ，那么 &inv[c] = inv[a] * inv[b] % MOD;
1、 &循环找解的方法
long long circleRun(long long n){
for(long long i = 1;i & MOD;i++)
if(i * n % MOD == 1)
return -1;
int main(){
while(cin && n){
cout && n && " 's inv is "&&
cout && circleRun(n) &&
2、费马小定理的解法 &MOD 是质数才能用
利用 & a ^ (p-1) % MOD === 1 , 那么它的逆元就是 & & a ^ (p-2)
#include&stdio.h&
#include&string.h&
#include&iostream&
#include&cmath&
const int MOD = 1e9+7;
long long quickpow(long long base,long long n){
long long ans = 1;
if(n%2 == 1) ans = ans * base % MOD;
base = base * base % MOD;
int main(){
while(cin && n){
cout && n && " 's inv is "&&
//cout && circleRun(n) &&
cout && " a ^ (p-2) % MOD "&&
cout && quickpow(n, MOD-2) &&
3、利用欧几里德扩展来求 ,
欧几里德扩展 是用来解决 &ax + by = gcd(a,b)这样的等式。
这时候取 &b = MOD, 你可以写成这样 &ax = gcd(a,b) - by
推导出 a*x % MOD = gcd(a,b) %MOD
所以只要 &gcd(a,b) % MOD === 1时,就可以使用这条来求a的逆元
但用exgcd求得时候,inv可能是负数， 还需要进行如下操作
inv = (inv % MOD + MOD) % MOD;
long long exGcd(long long a, long long b, long long &x0, long long &y0) // a*x0 + b*y0 = gcd(a,b)
long long r = exGcd(b, a % b, x0, y0);
long long t = x0;
y0 = t - a / b * y0;
int main(){
while(cin && n){
cout && n && " 's inv is "&&
//cout && circleRun(n) &&
cout && " a ^ (p-2) % MOD "&&
cout && quickpow(n, MOD-2) &&
cout && " ax + by = gcd(a,b) " &&
long long inv,y0;
exGcd(n ,MOD,inv,y0);
inv = (inv % MOD + MOD) % MOD;
cout && inv &&
4、利用某神奇推导。。 O(n)求出 1---- n 的所有逆元。&
预处理1-n关于p的逆元：（n & p） , 因为 逆元是积性函数，所以只要 p & n 成立即可，而不需要p必须为素数
& & & & &假设已经预处理了1-i-1的逆元，j的逆元设为F[j]
& & & & &令p = x * i &y ( 0 & y & i)
& & & & &X* i = y (mod p)
& & & & &X* F[y] * i = y * F[y] = 1(mod p)
& & & & &所以i的逆元是F[i] = X* F[y]
& & & & &这样就可以O(n)的时间预处理了。
const int N = 100005;
long long _inv[N];
void pre() {
_inv[0] = _inv[1] = 1;
for (int i = 2; i & N; i++) {
_inv[i] = ((MOD - MOD / i) * _inv[MOD % i]) % MOD;
int main(){
while(cin && n){
cout && _inv[n] &&
4、 利用逆元函数是完全积性函数的性质
求所有质数的逆元即可，预处理复杂度是O(n / logn * logn) = O(n)
这种写法可以用 exgcd 来实现素数的logn 求逆,因为此时 &a = p , &MOD无论取何值(p除外) &, &都有 &gcd(p ,mod) = 1,适合通用情况。
之后再采取质因数分解的方法，即可对任意一个 n 以 logn速度求出其逆元&
不过。。ACM竞赛如果为了求逆写这么长的代码貌似不太现实。
Views(...) Comments()