POJ 2142 扩展欧几里得

这题问的是|x|+|y|最小的时候 讨论一下当取x最小正整数解的时候 通过x求出y 当y取最小正整数解的时候通过y求出x 

只有这两种情况因为情况的x和y都比这两种情况的大  所以只需要比较这两种情况的特解就可以得出答案

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;

void exgcd(long long a,long long b,long long &d,long long &x,long long &y)
{
    if(b==0)
    {
        x=1,y=0,d=a;
        return;
    }
    exgcd(b,a%b,d,x,y);
    long long temp=x;
    x=y;
    y=temp-(a/b)*y;
}
long long absn(long long a)
{
    return a>=0?a:-a;
}
int main()
{
    long long a,b,d,x,y,c,s,x1,y1,x2,y2;
    while(~scanf("%lld%lld%lld",&a,&b,&c),a+b+c)
    {
        exgcd(a,b,d,x,y);
        x1=(x*(c/d)%(b/d)+(b/d))%(b/d);
        y1=absn((c-x1*a)/b);
        y2=(y*(c/d)%(a/d)+(a/d))%(a/d);
        x2=absn((c-b*y2)/a);
        if(x1+y1<x2+y2)
            printf("%lld %lld\n",x1,y1);
        else
            printf("%lld %lld\n",x2,y2);
    }
    return 0;
}