拓展欧几里德算法

对于 \(ax+by=c\) (其中 \(a,b,c\) 已知),要求整数解(不一定是正数) \(x,y\).

根据裴蜀定理 \(\forall a,b,\exists x,y,\ 使 ax+by=g,(其中g=gcd(a,b))\)
\(ax+by=c\) 等式两边同时除以 \(g\)
得 \(a^{‘}x+b^{‘}y=c/g\),如果 \(c\ 不能被\ g\ 整除\) ,则等式右边为分数,左边为整数,显然无解.
如果\(\ c\ 能被\ g\ 整除\),设 \(c=kg\) ,只需求出 \(ax+by=g\) 的解,再乘以 \(k\) 即可.只需应用拓展欧几里得即可求解.所以我们以后只考虑 \(ax+by=g\) 的解,只需把这个式子的解再乘以 \(k\) 即可.
拓展欧几里德算法模板

void gcd(int a,int b,int &d,int &x,int &y)
{
	if(!b){d=a;x=1;y=0;}
	else { gcd(b,a%b,d,y,x);y -= x*(a/b);}
}

应用上面的算法已经求出了一组\(\{x_1,y_1\}\),那么如何求出所有的解呢?
设还有一组解 \(x_2,y_2\).那么有\(ax_1+by_1=ax_2+by_2=g\),移项得 \(a(x_1-x_2)=b(y_2-y_1)\),等式两边除以 \(g\) ,有 \(a^{‘}(x_1-x_2)=b^{‘}(y_2-y_1)\),考虑到 \(a^{‘}与b^{‘}\)互质,因此一定有\((x_1-x_2)=kb^{‘},(y_2-y_1)=ka^{‘}\),所以\(x=x_0+kb^{‘},y=y_0-kb^{‘},k\in Z\)

原文地址：http://www.cnblogs.com/oijueshi/p/16817283.html