1. The simplest approach does not have rolling separation, namely GCD (A, B) = GCD (A, A% B).
Simple proof is as follows:
Set K is a, b, then k | a, k | b, because r = a% B, 即 = N * b r, by k | a, k | b, then k | r, then K is a common cause of A and R.
K is a, r, and K | A, K | R, K | B, K | B, which is known from A = N * B R, and k is a male passenger.
The specific procedures are as follows (C )
Template
T GCD (t a, t b)
{
While (b! = 0)
{
T r = a% b;
A = B;
B = R;
}
Return A;
}
2.Tein algorithm
The basic principles are as follows: (Set the maximum number of conventions to D, where you need to recurrent, use AN, BN, DN)
1) If a = 0, D = B
2) If b = 0, D = a
3) If 2 | A && 2 | B, then 2 is the number of conventions, take A1 = A / 2, B1 = B / 2, D1 = 2d (AN 1 = AN / 2, BN 1 = BN / 2, DN 1 = DN * 2)
4) If 2 | A && B is not an even number, then 2 is not the number of conventions, so AN 1 = AN / 2, BN 1 = BN, DN 1 = DN
5) If 2 | B && A is not an even number, then 2 is not the number of conventions, so AN 1 = A, BN 1 = BN / 2, DN 1 = DN
6) If a, b is not even, then AN 1 = | AN-BN |, BN 1 = min (AN, BN), DN 1 = DN, That is GCD (| AN-BN |, MIN) , BN)) = GCD (AN, BN), which proves the method used in the same mutation.
Simple implementation is as follows:
Template
T Stein_GCD (Const T & A, Const T & B)
{
IF (a == 0)
{
Return B;
}
Else IF (b == 0)
{
Return A;
}
ELSE IF (a% 2 == 0 && b% 2 == 0)
{
Return 2 * Stein_GCD (A / 2, B / 2);
}
ELSE IF (a% 2 == 0 && B% 2! = 0)
{
Return Stein_GCD (A / 2, B);
}
ELSE IF (a% 2! = 0 && B% 2 == 0)
{
Return Stein_GCD (A, B / 2);
}
Else
RETURN Stein_GCD (MAX (A, B) -min (A, B), MIN (A, B));
}
Simple recursive, the total sensation algorithm is not idealized, and it is expected to be improved.
