P5656 【模板】二元一次不定方程 (exgcd)

· · 题解

观前提示

本题解不由 exgcd 算法实现。

做法说明

首先注意到 a,b,c \ge 1。

1. 判断无解

若 c \bmod \gcd(a,b)=0 时才有解。

为什么呢？

设式子为 ax+by=c，\gcd(a,b)=d。

即原式可表达为 d(tx+py)=c，t,p 为一整数使得 td=a, pd=b。

因为要使得式子有整数解，t,x,p,y 必须都是整数，所以 c \bmod d=0 才有可能有此类解。

2. 辗转相除法

将式子简化为 ax+by=1，其中 a 与 b 互质。

使用辗转相除法求得不完全商数组，证明留给下面。

3. 通解

使用不完全商数组求得 ax+by=1 的解，并将答案乘以 c，取得原式的解。

4. 细节

设通解为 xx,yy。

将解表达为 xx \pm tb, yy \pm ta 的形式，其中 t=\pm1,2,3\dots，并提升至最小/最大解。

具体细节看代码。

Code

时间复杂度为 \log 级别，常数略大。

#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
using namespace std;
using i64 = long long;
int n,t,cnt=1;
int q[40],p[40],Q[40];
pair<int,int> ans;
void divi(int x, int y){
    while(x>1 && y>1){
        q[cnt++]=x/y;
        x-=(x/y)*y;
        swap(x,y);
    }
}

pair<int, int> solve2(int a, int b, int c){
    divi(a,b);
    if(a==1){auto ans=mp(c,0);return ans;}
    if(b==1){auto ans=mp(0,c);return ans;}
    p[0]=1;p[1]=q[1];
    for(int i=2;i<cnt;i++) p[i]=q[i]*p[i-1]+p[i-2];
    Q[0]=0;Q[1]=1;
    for(int i=2;i<cnt;i++) Q[i]=q[i]*Q[i-1]+Q[i-2];
    int x=((cnt-2)%2?-1:1)*Q[cnt-1],y=((cnt-1)%2?-1:1)*p[cnt-1];
    auto ans=mp(x*c,y*c);
    return ans;
}

void solve(){
    for(int i=0;i<cnt;i++) p[i]=q[i]=Q[i]=0;
    cnt=1;int a,b,c;cin>>a>>b>>c;
    int gcd=__gcd(abs(a),abs(b));
    if(c%gcd!=0){cout<<"-1\n"; return;} 
    if(gcd!=1){
        a/=gcd,b/=gcd,c/=gcd; //将原式化成最简
        int absa=abs(a),absb=abs(b),absc=abs(c);
        ans=solve2(absa,absb,absc);
    }else{ans=solve2(a,b,c);}
    int x0=ans.first,y0=ans.second;
    if(a<0) x0=-x0;if(b<0) y0=-y0;
    int minx=x0%b,miny=y0%a;minx=(minx<=0?minx+b:minx);miny=(miny<=0?miny+a:miny);    int maxx=(c-b*miny)/a, maxy=(c-a*minx)/b; //将通解提升至最小x/y解，并通过最小解求出最大解。
    if(maxx<=0 || maxy<=0){cout<<(c-b*maxy)/a<<" "<<(c-a*maxx)/b<<endl;return;} //若最大解<0，则无正整数x,y解。
    cout<<(maxx-minx)/b+1<<" "<<minx<<" "<<miny<<" "<<maxx<<" "<<maxy<<endl; //(maxx-minx)/b+1即为正整数解的数量。
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>t;
    while(t--) solve();
    // 解的数量 = min((c/a-最小x)/b+1, (c/b-最小y)/a+1)
    return 0;
}

证明

选自《初等数论》第三版，高等教育出版社。