【算法】初等数论

初等数论

模

取余，遵照尽可能让商向0靠近的原则，结果的正负和左操纵数相同
取模，遵照尽可能让商向负无穷靠近的原则，结果的正负和右操纵数相同
7/（-3）=-2.3，产生了两个商-2和-3，取余语言中取-2，导致余数为1；取模语言中取-3，导致余数为-2
   java中%是取余
  幂

1、暴力幂

头脑：直接将a连续乘以b遍
时间复杂度：O（n）
空间复杂度：O（1）

1.     // 求 a^b
2.     public long pow(int a, int b){
3.         long ans = 1;
4.         for (int i = 0; i < b; i++) {
5.             ans *= a;
6.         }
7.         return ans;
8.     }

复制代码

2、快速幂

头脑：利用幂的2进制形式来加速运算。
时间复杂度：O(log₂N)
空间复杂度：O（1）

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

复制代码

  例子：
                                                     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类

1. // 求 a^b
2. // java.lang.Math
3. // double pow(double a, double b)
4. Math.pow(a, b)

复制代码

  可以支持浮点数的幂
  增补

结果%c

原理：多个数的积%c，便是下列操纵和的结果

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

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

复制代码

对数

1、Math类

1. //java.lang.Math
2. double log(double a) //以e为底
3. double log10(double a) //以10为底
5. Math.log(n);
6. Math.log10(n);

复制代码

  可以求浮点数的对数
  2、朴素

1.     public static int logN(int base, int n) {
2.         int power = 0;
3.         while (n / base > 0) {
4.             n = n / base;
5.             power++;
6.         }
7.         return power;
8.     }
10.         //log2
11.     public int log2(int n) {
12.         int power = 0;
13.         while ((n = n >> 1) > 0) {
14.             power++;
15.         }
16.         return power;
17.     }

复制代码

矩阵

1、单位矩阵

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

1.         public int[][] unit(int n){
2.         int[][] res=new int[n][n];
3.         for(int i=0;i<n;i++){
4.             res[i][i]=1;
5.         }
6.         return res;
7.     }

复制代码

2、乘法

1.         public int[][] multiplyMatrix(int x1[][],int x2[][]){
2.         //第一个矩阵的列必须等于第二个矩阵的行
3.         if(x1[0].length!=x2.length){
4.             return;
5.         }
6.         int lineLength=x1.length;   //第一个矩阵的行
7.         int listLength=x2[0].length;//第二个矩阵的列
8.         int[][] multiply=new int[lineLength][listLength];//相乘的结果矩阵
9.         for(int i=0;i<lineLength;i++){
10.             for(int j=0;j<listLength;j++){
11.                 for(int k=0;k<x1[0].length;k++){
12.                     multiply[i][j]+=x1[i][k]*x2[k][j];
13.                 }
14.             }
15.         }
16.         return multiply;
17.     }

复制代码

  矩阵%c便是矩阵上的每一个元素都%c
  3、快速幂

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

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

复制代码

素数（质数）

质数：是指在大于1的整数中，除了1和它本身以外不再有其他因数的自然数。
合数：是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。
1既不属于质数也不属于合数。最小的合数是4，最小的质数是2
1、朴素

1. boolean isPrime(int n){
2.         for(int i=2;i*i<=n;i++){
3.                 if(n%i==0){
4.                         return false;
5.                 }
6.         }
7.         return true;
8. }

复制代码

2、埃氏筛法

1.         //埃氏筛选法
2.     public void eratosthenes(int n) {
3.         boolean[] isPrime = new boolean[n+1];//false代表是素数，true代表的是合数
4.         for (int i = 0; i <= n; i++) {
5.             if(i<2){
6.                 isPrime[i]=true;
7.                 continue;
8.             }
9.             //如果是素数
10.             if (!isPrime[i]) {
11.                 //将该素数的所有倍数都标记为合数
12.                 for (int j = 2 * i; j < n; j += i) {
13.                     isPrime[j] = true;
14.                 }
15.             }
16.         }
17.     }

复制代码

  埃拉托斯特尼筛法（简称埃氏筛或爱氏筛）：要得到自然数n以内的全部素数，必须把不大于 根号n 的全部素数的倍数剔除，剩下的就是素数。
  时间复杂度：O(nloglogn)
  不足之处：6 在 indexI = 2 时被标记，而在 indexI = 3 时，又被标记了一次。存在重复标记，有优化空间
  3、欧拉筛

欧拉筛是对埃氏筛的改进，避免重筛，进步服从

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

复制代码

  欧拉筛法：包管每个合数只会被它的最小质因数筛掉，时间复杂度降低到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。
  

1. int gcd(int x, int y) {
2.         return x == 0 ? y : gcd(y % x, x);
3. }
5. int gcd(int a, int b){
6.     if (b == 0)
7.         return a;
8.     else
9.         return gcd(b, a%b);
10. }
12. int gcd(int a, int b){
13.     int temp;
14.     while(b!=0){
15.         temp=a%b;
16.         a=b;
17.         b=temp;
18.     }
19.     return a;
20. }

复制代码

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

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

1. int gcd(int x, int y) {
2.         if (x==y)return x;
3.         else if (x>y)return gcd(x-y,y);
4.         else return gcd(y-x,x);
5. }

复制代码

  更相减损法和辗转相除法的头脑较为接近，不同的是辗转相除法迭代更快，而更相减损法迭代慢。但后者使用的是减法，前者使用的是求余，前者损耗较低。在两数相差较大时避免使用更相减损法，而在大数是避免使用辗转相除法。
  最小公倍数（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∣​

1. int lcm(int a, int b) {
2.     return a * b / gcd(a, b);
3. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。