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