1
int ext_euclid(int a,int b,int &x,int &y)
2
{
3
int t,d;
4
5 if (b==0)
6
{
7 x=1;
8 y=0;
9 return a;
10
}
11
12 d=ext_euclid(b,a% b, x, y);
13 t= x;
14 x= y;
15 y=t-a/ b* y;
16
17 return d;
18
}
19
20
21int GCD( int a, int b )
22{
23 if ( a< b )
24 {
25 int temp= a;
26 a= b;
27 b= temp;
28 }
29
30 if ( b== 0 ) return a;
31 if ( b% 2== 0 && a% 2== 0 ) return 2* GCD( a/ 2, b/ 2 );
32 if ( b% 2== 0 && a% 2!= 0 ) return GCD( a, b/ 2 );
33 if ( b% 2!= 0 && a% 2== 0 ) return GCD( a/ 2, b );
34
35 return GCD( (a+ b)/2, (a- b)/ 2 );
36}
posted on 2008-08-19 12:43
Darren 閱讀(179)
評論(0) 編輯 收藏 引用