【算法】初等数论

初等数论

模

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

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

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

java中%是取余

幂

1、暴力幂

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

时间复杂度：O（n）

空间复杂度：O（1）

    // 求 a^bpublic 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）

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

例子：

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

3、Math类

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

可以支持浮点数的幂

补充

结果%c

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

• 每个乘项%c
• 最终积%c

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

对数

1、Math类

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

可以求浮点数的对数

2、朴素

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

矩阵

1、单位矩阵

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

	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、乘法

	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的表示（矩阵中为单位矩阵），以及乘法的定义

    // 求 a^bpublic int[][] pow(int[][] A, int b){int[][] ans = unit(A.length);// 不断取幂的二进制形式中的最后一位并且将b不断右移（将b最后一位抛弃），直到幂最后变为0while(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、朴素

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

2、埃氏筛法

	//埃氏筛选法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、欧拉筛

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

	//欧拉筛选法public void euler(int n) {//建立一个bool类型的数组，以下标为要判断的数字 以该下标的值为素数的标志//若i是素数 则 isPrime[i]=falseboolean[] isPrime = new boolean[n+1];isPrime[0] = isPrime[1] = true;//数字0和1都不是素数，所以赋trueint[] 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，那么它只能乘以第一个素数 2for (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之间的最大公约数。辗转相除法的算法流程可以如下：

1. 计算a与b的余数r。
2. 如果r为0，则返回gcd = b。否则，转到步骤3。
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;elsereturn 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的最大公约数。依次递归下去，直到两个数相等。这相等两个数的值就是所求最大公约数。

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{\mid a\cdot b\mid }{gcd(a,b)}$

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