EXgcd&&逆元（2019.3.2训练）【2019.6.4再次更新！】

本次训练共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