【算法】初等数论
初等数论
模
取余，遵循尽可能让商向0靠近的原则，结果的正负和左操作数相同
取模，遵循尽可能让商向负无穷靠近的原则，结果的正负和右操作数相同
7/（-3）=-2.3，产生了两个商-2和-3，取余语言中取-2，导致余数为1；取模语言中取-3，导致余数为-2
java中
%是取余
幂
1、暴力幂
思想：直接将a连续乘以b遍
时间复杂度：O（n）
空间复杂度：O（1）
// 求 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）
// 求 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^{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}} 35=3101=31∗23+0∗22+1∗20=31∗23∗30∗22∗31∗20
3、Math类
// 求 a^b
// java.lang.Math
// double pow(double a, double b)
Math.pow(a, b)
可以支持浮点数的幂
补充
结果%c
原理：多个数的积%c，等于下列操作和的结果
- 每个乘项
%c - 最终积
%c
// 求 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.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;
}
//log2
public 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^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、朴素
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]=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的最大公约数。依次递归下去，直到两个数相等。这相等两个数的值就是所求最大公约数。
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、最大公因数法（最优）
l c m ( a , b ) = ∣ a ⋅ b ∣ g c d ( a , b ) lcm(a,b)=\frac{∣a⋅b∣}{gcd(a,b)} lcm(a,b)=gcd(a,b)∣a⋅b∣
int lcm(int a, int b) {
return a * b / gcd(a, b);
}