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;
}
