首页 > 代码库 > hdu 2669 Romantic
hdu 2669 Romantic
使用扩展的欧几里得算法。
对于初始的两个整数$x_1,y_1$，我们一定可以计算出$ax_1+by_1 = gcd(a,b)$，递推下一步，我们可以得到公式：
\begin{equation} ax_1+by_1 = gcd(a,b) = gcd(b,a\%b) = bx_2 + (a\%b)y_2 \end{equation}
从而解出$x_1 = y_2$和$y_1 = x_2-(a/b)y_2$。从而我们可以使用递归实现对扩展欧几里得的计算。
需要注意的是满足条件的解不唯一，对于任意的整数$k$，我们有$x = x+kb$，$y = y - ka$同样成立，答案求的是在众多解中的最小的正整数$x$和与其配对的$y$。
代码如下:
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #include <cstring> 5 using namespace std; 6 typedef long long LL; 7 void exgcd(LL a, LL b, LL &d, LL &x, LL &y) 8 { 9 if( b == 0 )10 {11 d = a;12 x = 1;13 y = 0;14 }15 else16 {17 exgcd(b, a%b, d, x, y);18 int t = x;19 x = y;20 y = t - (a/b)*x;21 }22 }23 int main(int argc, char *argv[])24 {25 LL x, y, d, a, b;26 while(cin>>a>>b)27 {28 exgcd(a, b, d, x, y);29 if( d == 1 )30 {31 while( x < 0 )32 {33 x += b;34 y -= a;35 }36 cout<<x<<" "<<y<<endl;37 }38 else39 {40 printf ( "sorry\n" );41 }42 }43 }
hdu 2669 Romantic
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。