线性丢番图方程

方程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;
}

a₁x₁+a₂x_2+......+a_nx_n=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;
}