首页 > 代码库 > 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