推荐文章:
1. 求解线性同余方程
2. 【洛谷日报#205】乘法逆元
3. 乘法逆元 - OI wiki

本次训练共5题,本文附AC代码和题目链接。

复习逆元时,发现之前在林大OJ过的代码在原题的OJ提交基本上都是错的,所以我又更新了这篇文章,改成了原题链接和原题的AC代码。以后还是找原题做吧,nefu的数据实在是太弱了,一个错误代码还能给你AC,随便出个数据就WA了好吧...
——————————————————————————————————————————————————————2019.6.4 更新。

做题之前,先给出线性求a对p的逆元inv(a,p)的两个模板,时间复杂度均为O(n)。

p必须要为质数才能使用这两个模板!!!比如求inv(5,12),这两个模板都不能用!!!

这里我们只讨论当模数为素数的情况,因为如果模数不为素数,则不一定每个数都有逆元(模数为合数时,可能有逆元也可能没有)。

如果模数不为质数,此时要求ax+by=1中x的最小整数解(实际上就是求a对b的逆元,b为合数),只能用exgcd!!!

模板1:递归求逆元

long long inv(long long a,long long p)
{return a==1?1:(p-p/a)*inv(p%a,p)%p;}

使用要求:
1.a、p互质
2.p为质数(比如9973,19260817)
3.a<p(要保证a<p,函数调用时写成inv(a%p,p)即可)
这三个条件必须同时满足才能保证逆元一定存在,否则有可能无限递归Runtime Error
比如inv(5,12),满足a、p互质且a<p,但是不满足p为质数,所以没有逆元inv(5,12),不能用这个模板

模板2:递推求逆元(逆元不存在也可使用,若逆元inv[i]不存在则inv[i]=0)

long long n,p,i,inv[1000010];
void get_inv()
{
    inv[1]=1;
    for(i=2;i<=n;i++)//n为能递推到的最大的a
    inv[i]=(p-p/i)*inv[p%i]%p;
}

使用要求:能递推到的最大的a不要超过1e6,否则请使用模板1或者用exgcd。
p不为质数, inv(5,12),不能用这个模板,用这个模板算出来是0,而实际上是5,一定要用exgcd!!!
开数组要过本地编译器最大能开1e8,但是oj过不了(Runtime Error: Segmentation fault)
开1e7会超过内存64512k(Memory Limit Exceeded)
开1e6,数据小的话一般能过

A题 hdu 1576 A/B

这题很友好,满足了使用模板1的条件:p为质数、gcd(b,p)=1,直接套模板就好啦~

#include <bits/stdc++.h>
using namespace std;
long long t,n,b,p=9973;
long long inv(long long a,long long p)
{return a==1?1:(p-p/a)*inv(p%a,p)%p;}
int main()
{
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n>>b;
        printf("%lld\n",n*inv(b%p,p)%p);
    }
    return 0;
}

E题 洛谷 P3811 乘法逆元

本题已经保证p为质数,要用模板1还需要保证a,b互质,写一个gcd函数,然而算gcd的过程中会超时...
以下代码的思路是不行的:

//TLE两个点,错误代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll inv(ll a,ll p)
{return a==1?1:(p-p/a)*inv(p%a,p)%p;}
ll gcd(ll a,ll b)
{return b?gcd(b,a%b):a;}
ll n,p;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>p;
    for(int i=1;i<=n;i++)
    {
        if(gcd(i,p)==1)printf("%lld\n",inv(i%p,p));
        else printf("0\n");
    }
    return 0;
}

只能用模板2,递推求逆元。注意会爆int,要用long long。
AC代码:

#include <bits/stdc++.h>
using namespace std;
const int N=3e6+10;
typedef long long ll;
ll n,p,inv[N];
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>p;
    inv[1]=1;
    for(int i=2;i<=n;i++)
        inv[i]=(p-p/i)*inv[p%i]%p;
    for(int i=1;i<=n;i++)
        printf("%lld\n",inv[i%p]);
    return 0;
}

B题 hdu 2669 Romantic

用exgcd模板求ax+by=c中x的最小正整数解,参考资料:https://blog.csdn.net/weixin_42165981/article/details/81185418
当c%gcd(a,b)=0时有解,否则无解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1;y=0;return a;}
    ll gcd=exgcd(b,a%b,x,y);//求出a,b的最大公约数
    ll tmp=x;x=y;y=tmp-a/b*y;
    return gcd;
}
ll cal(ll a,ll b,ll c)//计算ax+by=c中x的最小整数解
{
    ll x,y;
    ll gcd=exgcd(a,b,x,y);//求出a,b的最大公约数,同时得到x和y的一组特解
    if(c%gcd!=0)return -1;//代表无解
    x=x*c/gcd;
    b=b/gcd;
    ll ansx=x%abs(b);
    if(ansx<=0)ansx=ansx+b;
    return ansx;//求出x的最小整数解
}
int main()
{
    ios::sync_with_stdio(false);
    ll a,b,ansx;
    while(cin>>a>>b)
    {
        ll ansx=cal(a,b,1);
        if(ansx==-1)printf("sorry\n");
        else printf("%lld %lld\n",ansx,(1-ansx*a)/b);
    }
    return 0;
}

C题 洛谷 P1082 同余方程

求ax+by=1中x的最小正整数解,等价于求a对b的逆元,但是本题中的b不一定为素数,b不为素数的情况下也是可能有逆元的,如果用那线性求逆元的那两个模板就会RE,算不出来逆元,所以只能用exgcd的模板了,exgcd的时间复杂度是O(logn)。
所以本题就变成了hdu 2669 Romantic这题的简单版本,就是求ax+by=c中x的最小正整数解,其中c=1。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1;y=0;return a;}
    ll gcd=exgcd(b,a%b,x,y);//求出a,b的最大公约数
    ll tmp=x;x=y;y=tmp-a/b*y;
    return gcd;
}
ll cal(ll a,ll b,ll c)//计算ax+by=c中x的最小整数解
{
    ll x,y;
    ll gcd=exgcd(a,b,x,y);//求出a,b的最大公约数,同时得到x和y的一组特解
    if(c%gcd!=0)return -1;//代表无解
    x=x*c/gcd;
    b=b/gcd;
    ll ansx=x%abs(b);
    if(ansx<=0)ansx=ansx+b;
    return ansx;//求出x的最小整数解
}
int main()
{
    ios::sync_with_stdio(false);
    ll a,b;
    cin>>a>>b;
    printf("%lld\n",cal(a,b,1));
    return 0;
}

D题 洛谷 P2613 有理数取余

这题数据特别大,所以需要用字符串输入,同时还必须取模,剩下的再用exgcd求逆元即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,p=19260817;
inline ll read()
{
    ll s=0;
    string tmp;
    cin>>tmp;
    for(int i=0;i<tmp.length();i++)
        s=(s*10+tmp[i]-'0')%p;
    return s;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1;y=0;return a;}
    ll gcd=exgcd(b,a%b,x,y);//求出a,b的最大公约数
    ll tmp=x;x=y;y=tmp-a/b*y;
    return gcd;
}
ll cal(ll a,ll b,ll c)//计算ax+by=c中x的最小整数解
{
    ll x,y;
    ll gcd=exgcd(a,b,x,y);//求出a,b的最大公约数,同时得到x和y的一组特解
    if(c%gcd!=0)return -1;//代表无解
    x=x*c/gcd;
    b=b/gcd;
    ll ansx=x%abs(b);
    if(ansx<=0)ansx=ansx+b;
    return ansx;//求出x的最小整数解
}
int main()
{
    ios::sync_with_stdio(false);
    a=read();b=read();
    if(cal(b,p,1)==-1)printf("Angry!\n");
    else printf("%lld\n",a*cal(b,p,1)%p);
    return 0;
}

由于a、b取模后比较小,所以也可以用模板1求逆元,gcd判断是否有解。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,p=19260817;
ll inv(ll a,ll p)
{return a==1?1:(p-p/a)*inv(p%a,p)%p;}
ll gcd(ll a,ll b)
{return b?gcd(b,a%b):a;}
inline ll read()
{
    ll s=0;
    string tmp;
    cin>>tmp;
    for(int i=0;i<tmp.length();i++)
        s=(s*10+tmp[i]-'0')%p;
    return s;
}
int main()
{
    ios::sync_with_stdio(false);
    a=read();b=read();
    if(gcd(b,p)==1)printf("%lld\n",a*inv(b%p,p)%p);
    else printf("Angry!\n");
    return 0;
}

总结
扩展欧几里得、费马小定理+快速幂、线性求逆元是逆元的三种求法
1.扩展欧几里得:要求a、p互质,时间复杂度O(loga^p^)
2.费马小定理+快速幂:要求p必须是质数,时间复杂度O(log2^p^)
3.线性求逆元:要求p必须是质数,时间复杂度O( P )
如果求一个数的逆元,扩展欧几里得是最佳的选择,
如果需要N个数的逆元,线性递推式最好的方式,
费马小定理+快速幂似乎没什么用武之地,
后两种都是要求p是质数的,当p不是质数,但p和a互质时,可以选择扩展欧几里得

求逆元几种方法的总结还可以去看看这篇文章https://blog.csdn.net/fsahfgsadhsakndas/article/details/51027338