刚学习的扩展欧几里得算法，刷个水题
求解 线性不定方程 和 模线性方程
求方程 ax+by=c 或 ax≡c (mod b) 的整数解
1、ax+by=gcd(a,b)的一个整数解：
<span style="font-size:14px;">void ex_gcd(int a,int b,int &d,int &x,int &y)//扩展欧几里得算法
{
if(!b){d=a;x=1;y=0;}
else {ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}
}</span>2、ax+by=c的全部整数解：
方程两边同一时候乘以g/c(g为a，b的最大公约数)。则原方程为 g *a/c *x+g*b/c*y=g
则g*x/c=x0,g*y/c=y0 ( x0,y0为 方程ax+by=gcd(a,b)的一个特解）
所以原方程的一个特解x=x0*c/g,y=y0*c/g
求通解的过程省略。
。。
最后通解为 (x+kb1,y-ka1) b1=b/g,a1=a/g。
3、ax≡c (mod b)方程的全部整数解：
ax和c关于模b同余。则(ax-c)是b的整数倍。设倍数为y，则原方程等价于 ax-c=by,移项得 ax-by=c，转变为求解ax+by=c的形式
假设两个数的最大公约数为1。则两个数互质
题目分析：
给定 a b k找到满足ax+by=k 的令|x|+|y|最小（等时令a|x|+b|y|最小）最好还是a 〉b
先用扩展欧几里得算法求出 一组解 x0。y0，通解能够表示为x=x0+b/d *t y=y0-a/d *t
|x|+|y|=|x0+b/d *t |+|y0-a/d *t| 这个关于t的函数的最小值在 t = y0*d/a 附近的两整点里取。故直接验证这两点就可以。
由于 设a>b之后
|x0+b/d *t| 单调递增，|y0-a/d*t| 先递减再递增。
因斜率a/d>b/d。所以总的|x0+b/d *t |+|y0-a/d *t| 先递减再递增，使y0-a/d*t0=0 的t0附近有最小值。
//转载
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int x0,z1,a1,b1;
void ex_gcd(int a,int b,int &d,int &x,int &y)
{
if(!b){d=a;x=1;y=0;}
else {ex_gcd(b,a%b,d,y,x);y-=x*(a/b);}
}
int calx(int k)
{
return abs(x0+k*b1);
}
int caly(int k)
{
return abs(z1-k*a1);
}
int main()
{
int a,b,c;
while(~scanf("%d%d%d",&a,&b,&c)&&(a||b||c)){
int flag=1;
if(a<b) {flag=0;swap(a,b);}
int d,x,y,k,k1,k2;
ex_gcd(a,b,d,x,y);
x0=x*(c/d),z1=y*(c/d);
a1=a/d,b1=b/d,k1=z1/a1;
if(k1*a1-z1>=0) k1--;
k2=k1+1;
if(calx(k1)+caly(k1)>calx(k2)+caly(k2)) k=k2;
else if(calx(k1)+caly(k1)<calx(k2)+caly(k2)) k=k1;
else{
if(calx(k1)*a+caly(k1)*b>calx(k2)*a+caly(k2)*b) k=k2;
else k=k1;
}
int ansx=calx(k);
int ansy=caly(k);
if(!flag){
printf("%d %d
",ansy,ansx);
}
else printf("%d %d
",ansx,ansy);
}
return 0;
}