【算法】初等数论

初等数论

模

取余，遵循尽可能让商向0靠近的原则，结果的正负和左操作数相同

取模，遵循尽可能让商向负无穷靠近的原则，结果的正负和右操作数相同

7/（-3）=-2.3，产生了两个商-2和-3，取余语言中取-2，导致余数为1；取模语言中取-3，导致余数为-2

java中%是取余

幂

1、暴力幂

思想：直接将a连续乘以b遍

时间复杂度：O（n）

空间复杂度：O（1）

java">    // 求 a^b
    public long pow(int a, int b){
        long ans = 1;
        for (int i = 0; i < b; i++) {
            ans *= a;
        }
        return ans;
    }

2、快速幂

思想：利用幂的2进制形式来加速运算。

时间复杂度：O(log₂N)

空间复杂度：O（1）

java">    // 求 a^b
    public long pow(int a, int b){
        long ans = 1;
        // 不断取幂的二进制形式中的最后一位并且将b不断右移（将b最后一位抛弃），直到幂最后变为0
        while(b > 0){
            // 当前幂的最后一位为1，表明需要将该结果添加到最终的结果中（由于是幂中的+，实际上操作为乘法）
            if((b & 1) == 1){
                ans *= a;
            }
            // 将底数变为原底数的二次方
            a *= a;
            // 抛弃幂二进制形式的最后一位
            b >>= 1;
        }
        return ans;
    }

例子：

$3^{5}=3^{101}=3^{1*2^{3}+0*2^{2}+1*2^{0}}=3^{1*2^{3}}*3^{0*2^{2}}*3^{1*2^{0}}$

3、Math类

java">// 求 a^b
// java.lang.Math
// double pow(double a, double b)
Math.pow(a, b)

可以支持浮点数的幂

补充

结果`%c`

原理：多个数的积%c，等于下列操作和的结果

每个乘项%c
最终积%c

java">    // 求 a^b%c
    public long pow(int a, int b, int c){
        long ans = 1;
        // 不断取幂的二进制形式中的最后一位并且将b不断右移（将b最后一位抛弃），直到幂最后变为0
        while(b > 0){
            // 当前幂的最后一位为1，表明需要将该结果添加到最终的结果中（由于是幂中的+，实际上操作为乘法）
            if((b & 1) == 1){
                ans = (ans*a)%c;
            }
            // 将底数变为原底数的二次方
            a = (a*a)%c;
            // 抛弃幂二进制形式的最后一位
            b >>= 1;
        }
        return ans%c;
    }

对数

1、Math类

java">//java.lang.Math
double log(double a) //以e为底
double log10(double a) //以10为底

Math.log(n);
Math.log10(n);

可以求浮点数的对数

2、朴素

java">    public static int logN(int base, int n) {
        int power = 0;
        while (n / base > 0) {
            n = n / base;
            power++;
        }
        return power;
    }

	//log2
    public int log2(int n) {
        int power = 0;
        while ((n = n >> 1) > 0) {
            power++;
        }
        return power;
    }

矩阵

1、单位矩阵

单位矩阵的对角线上的元素全为1，其他的元素全为0

java">	public int[][] unit(int n){
        int[][] res=new int[n][n];
        for(int i=0;i<n;i++){
            res[i][i]=1;
        }
        return res;
    }

2、乘法

java">	public int[][] multiplyMatrix(int x1[][],int x2[][]){
        //第一个矩阵的列必须等于第二个矩阵的行
        if(x1[0].length!=x2.length){
            return;
        }
        int lineLength=x1.length;   //第一个矩阵的行
        int listLength=x2[0].length;//第二个矩阵的列
        int[][] multiply=new int[lineLength][listLength];//相乘的结果矩阵
        for(int i=0;i<lineLength;i++){
            for(int j=0;j<listLength;j++){
                for(int k=0;k<x1[0].length;k++){
                    multiply[i][j]+=x1[i][k]*x2[k][j];
                }
            }
        }
        return multiply;
    }

矩阵%c等于矩阵上的每一个元素都%c

3、快速幂

类似于整数的快速幂，不同的是1的表示（矩阵中为单位矩阵），以及乘法的定义

java">    // 求 a^b
    public int[][] pow(int[][] A, int b){
        int[][] ans = unit(A.length);
        // 不断取幂的二进制形式中的最后一位并且将b不断右移（将b最后一位抛弃），直到幂最后变为0
        while(b > 0){
            // 当前幂的最后一位为1，表明需要将该结果添加到最终的结果中（由于是幂中的+，实际上操作为乘法）
            if((b & 1) == 1){
                ans = multiplyMatrix(ans,a);
            }
            // 将底数变为原底数的二次方
            a = multiplyMatrix(a,a);
            // 抛弃幂二进制形式的最后一位
            b >>= 1;
        }
        return ans;
    }

素数（质数）

质数：是指在大于1的整数中，除了1和它本身以外不再有其他因数的自然数。

合数：是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。

1既不属于质数也不属于合数。最小的合数是4，最小的质数是2

1、朴素

java">boolean isPrime(int n){
	for(int i=2;i*i<=n;i++){
		if(n%i==0){
			return false;
		}
	}
	return true;
}

2、埃氏筛法

java">	//埃氏筛选法
    public void eratosthenes(int n) {
        boolean[] isPrime = new boolean[n+1];//false代表是素数，true代表的是合数
        for (int i = 0; i <= n; i++) {
            if(i<2){
                isPrime[i]=true;
                continue;
            }
            //如果是素数
            if (!isPrime[i]) {
                //将该素数的所有倍数都标记为合数
                for (int j = 2 * i; j < n; j += i) {
                    isPrime[j] = true;
                }
            }
        }
    }

埃拉托斯特尼筛法（简称埃氏筛或爱氏筛）：要得到自然数n以内的全部素数，必须把不大于根号n 的所有素数的倍数剔除，剩下的就是素数。

时间复杂度：O(nloglogn)

不足之处：6 在 indexI = 2 时被标记，而在 indexI = 3 时，又被标记了一次。存在重复标记，有优化空间

3、欧拉筛

欧拉筛是对埃氏筛的改进，避免重筛，提高效率

java">	//欧拉筛选法
    public void euler(int n) {
        //建立一个bool类型的数组，以下标为要判断的数字 以该下标的值为素数的标志
		//若i是素数 则 isPrime[i]=false
        boolean[] isPrime = new boolean[n+1];
        isPrime[0] = isPrime[1] = true;//数字0和1都不是素数，所以赋true
 
        int[] Prime = new int[n+1];//存放素数的数组
        int t = 0;
        Prime[t++] = 2;//把2放进素数表
        for (int i = 2; i <= n; i++) {
            if (!isPrime[i])//若当前数是素数
                Prime[t++] = i;//则存入素数数组
            // 每一个数都去乘以当前素数表里面已有的数，如果 indexI 是合数，且 indexI % primeList[indexJ] == 0，那么它只能乘以第一个素数 2
            for (int j = 0; j < t && Prime[j] * i <= n; j++) {
                isPrime[i * Prime[j]] = true;
                // 保证了每个合数只会被它的最小素因子筛掉,避免重筛,使得程序更有效率
                if (i % Prime[j] == 0)
                    break;
            }
        }
    }

欧拉筛法：保证每个合数只会被它的最小质因数筛掉，时间复杂度降低到O(n)。

每一个数都去乘以当前素数表里面 小于等于最小素因子的数

最大公因数（gcd）

最大公约数（Greatest Common Divisor）

1、辗转相除法（欧几里得）

思想：两个正整数a和b（a > b），它们的最大公约数gcd等于a除以b的余数r和b之间的最大公约数。辗转相除法的算法流程可以如下：

计算a与b的余数r。
如果r为0，则返回gcd = b。否则，转到步骤3。
使用b的值更新a的值，使用余数r更新b的值，转到步骤1。

int gcd(int x, int y) {
	return x == 0 ? y : gcd(y % x, x);
}

int gcd(int a, int b){
    if (b == 0)
        return a;
    else
        return gcd(b, a%b);
}

int gcd(int a, int b){
    int temp;
    while(b!=0){
        temp=a%b;
        a=b;
        b=temp;
    }
    return a;
}

根本无需判断a和b的大小，当a值小于b值时，算法的下一次递归调用就能够将a和b的值交换过来

2、更相减损术

思想：两个正整数a和b（a > b），它们的最大公约数等于a-b的差值c和较小数b的最大公约数。依次递归下去，直到两个数相等。这相等两个数的值就是所求最大公约数。

java">int gcd(int x, int y) {
	if (x==y)return x;
	else if (x>y)return gcd(x-y,y);
	else return gcd(y-x,x);
}

更相减损法和辗转相除法的思想较为接近，不同的是辗转相除法迭代更快，而更相减损法迭代慢。但后者使用的是减法，前者使用的是求余，前者损耗较低。在两数相差较大时避免使用更相减损法，而在大数是避免使用辗转相除法。

最小公倍数（lcm）

1、加穷举法

将大数依次乘N（N为从1开始的自然数），对得到的数判断其是否整除小数。

2、乘穷举法

将大数依次加1，对得到的数判断其是否可整除两数。

3、最大公因数法（最优）

$lcm(a,b)=\frac{∣a⋅b∣}{gcd(a,b)}$

java">int lcm(int a, int b) {
    return a * b / gcd(a, b);
}