算法题：SOJ1092: 欧几里得算法

一、BackGroud

在RSA密码体系中,欧几里得算法是加密或解密运算的重要组成部分。它的基本运算过程就是解 x*a=1(mod n) 这种方程。

二、The Problem

整个解的过程是这样的，我们用一个例子来说明。
当a＝1001 ，n＝3837时
方程为 x * 1001 = 1 (mod 3837)

求解过程：

3837 = 3 * 1001 + 834
1001 = 1 * 834 + 167
834 = 4 * 167 + 166
167 = 166 + 1

所以

1 = 167 - 166
= 167 - (834 - 4 * 167)
= 5 * 167 - 834
= 5 *(1001 - 834) - 834
= 5 * 1001 - 6 *834
= 5 * 1001 - 6 * (3837 -3 *1001)
= 23 * 1001 - 6 *3837

然后对等式两端同时除以模3837得

23 * 1001 = 1 (mod 3837)
于是 x ＝ 23
现在给出a和n，你能不能在最短的时间内解出这个方程呢？

三、输入

输入包括多组测试数据。每组测试数据对应输入的一行，每行包括两个整数a和n。1 当a＝n＝0时输入结束，这组数据不包括在需要计算的数据中。

四、输出

对应每组输入数据，输出最小的满足题意的解x。
注意:本题用搜索是不可能做出来的,所以…

五、样例输入

1001 3837
136468984 134548555
0 0

六、样例输出

23
112206854

七、源代码

#include
int d,x,y;
void extend_euclid(int a,int b)
{
     if(b==0)
     {
        d=a;x=1;y=0;
     }
     else
     {
         extend_euclid(b,a%b);
         int temp=x;
             x=y;
             y=temp-a/b*y;
     }
}        
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)==2&&(n||m))
    {
       if(n>m)
       n%=m;
       extend_euclid(m,n);
       if(y<0)
       printf("%d\n",y+m);
       else
       printf("%d\n",y); 
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31