hdu2669 扩展欧几里德 二元一次解不定方程
题意：
给出两个非负整数a,b 求x,y 使ax+by=1，而且x非负并最小的答案
题解：
朴素的欧几里德原理： gcd(a,b)=gcd(b,a mod b)
扩展欧几里德定理：
对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b的最大公约数，
必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。
令a>b
当b==0 ,x=1,y=0;
否则,根据朴素的欧几里德原理，有
a*x1+b*y1=b*x2+(a%b)*y2
=b*x2+(a-a/b*b)*y2=b*x2+a*y2- a/b*b*y2
所以，
x1=y2,y1=x2-(a/b)*y2;
x1,y1 就是所求值之一。
若x不是非负数，可让x+=b,y-=a（ 左边加上a*b再减a*b,等式依然成立 ），直到符合;
对题目中的gcd(a,b)==1才有解
代码如下：
#include<iostream>#include<cstdio>#include<cmath>using namespace std;__int64 a,b,c,d,x,y;__int64 exgcd(__int64 a,__int64 b){if(b==0){x=1;y=0;return a;}d=exgcd(b,a%b);__int64 xx=y,yy=x-(a/b)*y;x=xx;y=yy;return d;}int main(){c=1;while(scanf("%I64d%I64d",&a,&b)!=EOF){if(a%2==0&&b%2==0){printf("sorry\n");continue;}d=exgcd(a,b);if(d !=1){printf("sorry\n");continue;}while(x<0){x+=b;y-=a;}printf("%I64d %I64d\n",x,y);}return 0;}