1. 最大公约数
欧几里得算法(辗转相除法)求最大公约数(Greatest Common Divisor，GCD)的递归定理：对任意非负整数a和任意正整数b
欧几里得算法递归实现：
// 欧几里得算法递归实现
public static int gcd(int a, int b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
欧几里得算法非递归实现：
// 欧几里得算法非递归实现
public static int gcd(int a, int b) {
int r;
while (b > 0) {
r = a % b;
a = b;
b = r;
}
return a;
}
2. 最小公倍数
求最小公倍数代码实现：
// 求最小公倍数
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
3. 模取幂
模取幂：求一个数的幂对另一个数的模运算，
// 模取幂：Math.pow(a, b) % n
// a, b为非负整数，n为正整数
public static int modularExponentiation(int a, int b, int n) {
int c = 0;
int d = 1;
String binaryB = Integer.toBinaryString(b);
for (int i = 0; i < binaryB.length(); i++) {
c *= 2;
d = (d * d) % n;
if (binaryB.charAt(i) == '1') {
c++;
d = (d * a) % n;
}
}
return d;
}
