715
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;
}
最后更新：2017-04-04 07:03:38