练习一下数学知识了。。
【题目链接】click here~~
【题目大意】Find the nonnegative integer X and integer Y to satisfy X*a + Y*b = 1. If no such answer print "sorry" instead.
求满足式子的x和y否则输出“sorry”
【解题思路】扩展欧几里得的基础了,
扩展欧几里德算法是用来在已知a, b求解一组x,y,使它们满足 等式: ax+by = gcd(a, b) =d(解一定存在,根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。
译文详解:扩展欧几里得入门篇
代码:
/*HDU 2669 扩展欧几里得算法*/#include <bits/stdc++.h>using namespace std;int x,y,n,m,a,b,d;void gcdexted(int a,int b,int &d,int &x,int &y){if(!b){d=a;x=1;y=0;}else{gcdexted(b,a%b,d,y,x);y-=x*(a/b);}}int main(){ while(scanf("%d%d",&a,&b)!=EOF){gcdexted(a,b,d,x,y);if(d!=1) puts("sorry");else{while(x<0){x+=b;y-=a;}printf("%d %d\n",x,y);} } return 0;}
,我不去想是否能够成功,既然选择了远方,便只顾风雨兼程!