方程ax+by=c被称为二元线性丢番图方程
二元线性丢番图方程例题：洛谷P1516
使用拓展欧几里得算法求解x
注意：本题的拓展欧几里得算法函数需要是正数
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1;y=0;
return a;
}
ll d=gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}
ll n,m,x,y,L;
int main(){
cin>>x>>y>>m>>n>>L;
ll a=n-m,c=x-y;
if(a<0){
a=-a;
c=-c;
}
ll d=gcd(a,L,x,y);
if(c%d!=0)cout<<"Impossible";
else cout<<((x*(c/d))%(L/d)+(L/d))%(L/d);
return 0;
}
a1x1+a2x2+......+anxn=c被称为多元丢番图方程
多元丢番图方程例题：最大体积
先用裴蜀定理判定是否有解，再用完全背包计算可能的体积，最后从最大值倒序遍历求解答案
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e5+39+7;
int n,a[N];bool flag[N];
int gcd(int a,int b){
if(!b)return a;
return gcd(b,a%b);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
int Gcd=a[1];
for(int i=2;i<=n;i++)Gcd=gcd(Gcd,a[i]);
if(Gcd==1){
flag[0]=1;
for(int i=1;i<=n;i++){
for(int j=a[i];j<=N;j++){
if(flag[j-a[i]])flag[j]=1;
}
}
for(int i=N;i>=0;i--){
if(!flag[i]){
cout<<i;
break;
}
}
}else cout<<0;
return 0;
}