最大公約數(shù)
說到求兩個最大公約數(shù)，我們很容易用以下的方法來求：
public class 整數(shù)1_最大公約數(shù) {
public static void main(String[] args) {
int a = 15;
int b = 40;
for (int i = a; i >= 1; i--) {
if (a % i == 0 && b % i == 0) {
System.out.println(i);
break;
}
}
}
}
這個方法非常簡單，但是兩個非常大的數(shù)字進(jìn)行比較的時(shí)候，這個方法效率是非常低的舆乔，所以要想別的方法。
根據(jù)最大公約數(shù)剂公，我們還有另一種方法——輾轉(zhuǎn)相除法希俩。
兩個整數(shù)的最大公約數(shù)是能夠同時(shí)整除它們的最大的正整數(shù)。輾轉(zhuǎn)相除法基于如下原理：兩個整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)的相除余數(shù)的最大公約數(shù) 诬留。
假設(shè)兩個整數(shù)為a和b斜纪，他們的公約數(shù)可以表示為gcd(a,b)。如果gcd(a,b) = c,則必然a = mc和b = nc文兑。a除以b得商和余數(shù)，余數(shù)r可以表示為r = a - bk腺劣，k這里是系數(shù)绿贞。因?yàn)閏為 a和b的最大公約數(shù)，所以c也一定是r的最大公約數(shù)橘原，因?yàn)?code>r = mc - nck = (m-nk)c籍铁。
因此gcd(a,b) = gcd(r,b)涡上，相當(dāng)于把較大的一個整數(shù)用一個較小的余數(shù)替換了，這樣不斷地迭代拒名，直到余數(shù)為0吩愧，則找到最大公約數(shù)。
即[a,b]--[b%a,a] [15,40]--[10,15]--[5,10]--[0,5] 5為最大公約數(shù)
舉例兩個整數(shù)為1071和462：
第一步：1071 / 462 = 2 * 462 + 147
第二步：462 / 147 = 3 * 147 + 21
第三步：147 / 21 = 7 * 21 + 0
此時(shí)余數(shù)為零增显，則21為兩個數(shù)的最大公約數(shù)雁佳。
如果還是理解不透，可以看下面的動畫演示同云。
兩條線段分別表示252和105糖权，其中每一段表示21。動畫演示了循環(huán)從大數(shù)中減去小數(shù)炸站，直到其中一段的長度為0星澳，此時(shí)剩下的一條線段的長度就是252和105的最大公約數(shù)。
條形表示法：
所以旱易，根據(jù)代碼如下:
public class 整數(shù)1_輾轉(zhuǎn)相除法 {
public static void main(String[] args) {
int a = 15, b = 40;
boolean whiletrue = true;
while (whiletrue) {
if (a == 0) {
System.out.println(b);
break;
}
int t = a;
a = b % a;
b = t;
}
}
}
此外禁偎，我們可以通過遞歸來實(shí)現(xiàn)：
public class 整數(shù)1_輾轉(zhuǎn)相除法 {
public static void main(String[] args) {
int a = 15, b = 40;
System.out.println(gcd(a,b)); //5
System.out.println(gcd(b,a)); //5
}
public static int gcd(int a,int b){
if(a==0)
return b;
return gcd(b%a,a);
}
}
最小公倍數(shù)
既然會求最大公約數(shù)，那么我們?nèi)绾吻笞畲蠊稊?shù)阀坏？
最小公倍數(shù)=兩整數(shù)的乘積÷最大公約數(shù)
即a*b/gcd(a,b)就可以了如暖。
public class 整數(shù)1_輾轉(zhuǎn)相除法 {
public static void main(String[] args) {
int a = 15, b = 40;
System.out.println(a * b / gcd(a, b)); //120
}
public static int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
}
求a的n次冪
public class 整數(shù)2_求a的n次冪 {
public static void main(String[] args) {
System.out.println(f(3, 5));
}
public static long f(int a, int n) {
long x = 1;
for (int i = 0; i < n; i++) {
x = x * a;
}
return x;
}
}
那么求a的n次冪對p取模呢？
public class 整數(shù)3_求a的n次冪對p取模 {
public static void main(String[] args) {
System.out.println(f(3, 50, 17));
}
public static long f(int a, int n,int p) {
long x = 1;
for (int i = 0; i < n; i++) {
x = x * a;
}
return (int)(x % p);
}
}
但這個效率并不高全释，而且還要考慮整數(shù)溢出的問題装处。
這時(shí)，我們應(yīng)該考慮整數(shù)取模的性質(zhì)和公式：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
a ^ b % p = ((a % p)^b) % p
我們可以考慮使用第三個公式浸船，邊循環(huán)邊取模妄迁。
這是x可以直接用int類型了。
代碼如下：
public class 整數(shù)2_求a的n次冪對p取模 {
public static void main(String[] args) {
System.out.println(f(3, 4, 17));
}
public static long f(int a, int n, int p) {
int x = 1;
for (int i = 0; i < n; i++) {
x = (x * a) % p;
}
return (x % p);
}
}
