HDU 2669 Romantic(扩展欧几里德, 数学题)

题目

//第一眼看题目觉得好熟悉,但是还是没想起来
//洪湖来写不出来去看了解题报告,发现是裸的 扩展欧几里得 - -

/*

//扩展欧几里得算法(求 ax+by=gcd )
//返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
#define LL long long
LL extend_gcd(LL a,LL b,LL &x,LL &y){
if(a==0&&b==0) return -1;//无最大公约数
if(b==0){x=1;y=0;return a;}
LL d=extend_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
}

*/

/*
//扩展欧几里德 模版二
void ex_gcd(__int64 a, __int64 b, __int64 &d, __int64 &x, __int64 &y)
{
if(!b){ d = a; x = 1; y = 0;}
else
{
ex_gcd(b, a%b, d, y, x);
y -= x*(a/b);
}
} //ex_gcd

*/

//猜测:如果两者的最大公约数不是1,那么就无法达成目的,输出sorry。。。
//猜测正确^-^

//x>=0

//a * x + b * y = 1
//-> a*(x+b) + b*(y-a) = a*x + a*b + b*y - a*b = 1

#include<math.h>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std; //返回d=gcd(a,b);和对应于等式ax+by=d中的x,y
#define LL __int64
LL extend_gcd(LL a,LL b,LL &x,LL &y){
if(a==&&b==) return -;//无最大公约数
if(b==){x=;y=;return a;}
LL d=extend_gcd(b,a%b,y,x);
y-=a/b*x;
return d;
} int main()
{
LL a, b, x, y, d;
while(scanf("%I64d%I64d",&a,&b)!=EOF)
{
d = extend_gcd(a, b, x, y);
if(d == )
{
while(x<)//output nonnegative integer X and integer Y
{
//a * x + b * y = 1
//-> a*(x+b) + b*(y-a) = a*x + a*b + b*y - a*b = 1
x = x+b;
y = y-a;
}
printf("%I64d %I64d\n",x,y);
}
else
{
printf("sorry\n");
} } return ; }
上一篇:HDU 2669 Romantic 扩展欧几里德---->解不定方程


下一篇:如何将根文件系统制作成yaffs格式,并设置从yaffs启动