整数的基本性质与运用

最大公约数

说到求两个最大公约数，我们很容易用以下的方法来求：

public class 整数1_最大公约数 {
    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;
            }
        }
    }
}

这个方法非常简单，但是两个非常大的数字进行比较的时候，这个方法效率是非常低的，所以要想别的方法。

根据最大公约数，我们还有另一种方法——辗转相除法。
两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数 。
假设两个整数为a和b，他们的公约数可以表示为gcd(a,b)。如果gcd(a,b) = c,则必然a = mc和b = nc。a除以b得商和余数，余数r可以表示为r = a - bk，k这里是系数。因为c为 a和b的最大公约数，所以c也一定是r的最大公约数，因为r = mc - nck = (m-nk)c。

因此gcd(a,b) = gcd(r,b)，相当于把较大的一个整数用一个较小的余数替换了，这样不断地迭代，直到余数为0，则找到最大公约数。

即[a,b]--[b%a,a] [15,40]--[10,15]--[5,10]--[0,5] 5为最大公约数

举例两个整数为1071和462：
第一步：1071 / 462 = 2 * 462 + 147
第二步：462 / 147 = 3 * 147 + 21
第三步：147 / 21 = 7 * 21 + 0
此时余数为零，则21为两个数的最大公约数。

如果还是理解不透，可以看下面的动画演示。

两条线段分别表示252和105，其中每一段表示21。动画演示了循环从大数中减去小数，直到其中一段的长度为0，此时剩下的一条线段的长度就是252和105的最大公约数。

条形表示法：

image.png

所以，根据代码如下:

public class 整数1_辗转相除法 {
    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;
        }
    }
}

此外，我们可以通过递归来实现：

public class 整数1_辗转相除法 {
    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);
    }
}

最小公倍数

既然会求最大公约数，那么我们如何求最大公倍数？
最小公倍数=两整数的乘积÷最大公约数
即a*b/gcd(a,b)就可以了。

public class 整数1_辗转相除法 {
    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 整数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 整数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);
    }
}

但这个效率并不高，而且还要考虑整数溢出的问题。
这时，我们应该考虑整数取模的性质和公式：
(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

我们可以考虑使用第三个公式，边循环边取模。
这是x可以直接用int类型了。
代码如下：

public class 整数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);
    }
}