二進制一次不定方程的整數解（擴充歐幾裡得算法）

（不得不說這是一堂數學*信競課）

整數解解法

c(mod b)或ax+by=c有整數解當且僅當（a,b）|c

一般意義下的解法：

歐拉函數

擴充歐幾裡得算法

代碼實作

exgcd傳回值為（a,b）

int exgcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1,y=0;
		return a;
	}
	int r=exgcd(b,a%b,y,x);
	y-=x*(a/b);
	return r;
}
           

（x,y為特解）

通解：

符合要求的特解的尋找

 例1. x最小的非負整數值 

解：找到x最接近于0的點後往前後枚舉

例2. |x+y|最小的解

解：将ax+by=c化成y=kx+b，那麼|x+y|=|(k+1)x+b|，寫出分段函數（兩段）

例3. m|x|+n|y|最小/大的解

解：m|x|+n|y|=m|x|+n|kx+b|，寫出分段函數（最多三段）

例4. x,y均為正數，mx+ny最小/大

解：mx+ny=(kn+m)x+bn，根據kn+m的正負性讨論即可。