P5656 【模板】二元一次不定方程 (exgcd)
整理一下關(guān)于 exgcd 的內(nèi)容，都說寫完這道題就會做所有 exgcd 的題了，是不是我不知道，反正今天又做了一遍，記錄一下我的過程，感覺沒有太難。
題意
求不定方程 \(ax+by=c\) 的解。
以下稱正整數(shù)解為 \(x,y\) 都是正整數(shù)的解，其中有一個是非正整數(shù)就不行。
如果沒有任何整數(shù)解，輸出 -1。
如果有正整數(shù)解，輸出個數(shù)，x_min，y_min，x_max，y_max。
如果沒有正整數(shù)解，輸出 x 正整數(shù)解的 x_min，y 正整數(shù)解的 y_min。
接下來分三步進行：求出基本量，處理情況二，處理情況三。
求出基本量
先把無解判了：\(c\% gcd(a,b)\ne 0\)，裴蜀定理，沒啥好說的。
之后使用 exgcd 求出一組特殊解 \(x_0\), \(y_0\)。
不定方程的解我們就可以刻畫出來了。
\(x'=x_0+\frac{b}{gcd(a,b)}\times t\)
\(y'=y_0-\frac{a}{gcd(a,b)}\times t\)
根據(jù)我的習(xí)慣，我將稱呼 \(\frac{b}{gcd(a,b)}\) 為 \(lenx\)，\(\frac{a}{gcd(a,b)}\) 為 \(leny\)，因為這個就像是一塊一塊的長度，方便接下來的推導(dǎo)。
如果想要知道 \(x,y\) 的極值情況明顯就可以利用 \(t\) 了。
我們求出來 \(t_{min}\) 和 \(t_{max}\)，利用 \(x,y\) 是正整數(shù)解的性質(zhì)列出來兩個式子。
不難求出來，懶得寫了，注意上下取整問題。
直接判斷 \(t_{min}\) 是不是大于 \(t_{max}\) 就行，如果是就是情況二。
情況二&&情況三
情況二：
經(jīng)典問題，根據(jù)通解的式子可以得出一個變量的最小非負整數(shù)解，特判一下 0 就行了。
情況三：
數(shù)量就是 \(t_{max}-t_{min}+1\)，按照通解式子搞就行。
代碼
點擊查看代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
int Exgcd(int a, int b, int &x, int &y){
if(!b){x=1; y=0; return a;}
int d=Exgcd(b,a%b,y,x);
y-=(a/b)*x; return d;
}
int Gcd(int a, int b){
if(!b) return a;
return Gcd(b,a%b);
}
void Solve(int a, int b, int c){
int d=Gcd(a,b);
if(c%d){cout<<-1<<'\n'; return;}//type 1
int x_gcd, y_gcd, x_0, y_0;
Exgcd(a,b,x_gcd,y_gcd);
x_0=x_gcd*c/d; y_0=y_gcd*c/d;
int lenx=b/d, leny=a/d;
int t_min, t_max;
t_min=ceil((double)1.0*(-x_0+1)/lenx);
t_max=floor((double)1.0*(y_0-1)/leny);
if(t_min>t_max){//type 3
int x_min, y_min;
x_min=(x_0%lenx+lenx)%lenx;
y_min=(y_0%leny+leny)%leny;
if(x_min==0) x_min=lenx;
if(y_min==0) y_min=leny;
cout<<x_min<<" "<<y_min<<'\n';
}else{//type2
cout<<t_max-t_min+1<<" ";
cout<<x_0+lenx*t_min<<" ";
cout<<y_0-leny*t_max<<" ";
cout<<x_0+lenx*t_max<<" ";
cout<<y_0-leny*t_min<<'\n';
}
return;
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T; cin>>T; while(T--){
int a, b, c;
cin>>a>>b>>c;
Solve(a,b,c);
}
return 0;
}
浙公網(wǎng)安備 33010602011771號