数学相关

1.大数相乘

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。 leetcode 43

输入: num1 = "123", num2 = "456"
输出: "56088"

模拟竖式运算

1. 乘数A位数为 m，乘数B位数为 n， A * B 结果 res 最大总位数为 m + n
2. A[i] * B[j] 的结果为 num( 位数为两位，”0x”,”xy”的形式)，其第一位位于 res[i+j]，第二位位于 res[i+j+1]

3. 计算结果时，如果第一位为0，需要去除

   public String multiply(String num1, String num2) {
    if("0".equals(num1) || "0".equals(num2)) return "0";
    int m = num1.length();
    int n = num2.length();
    int[] res = new int[m + n];
    for(int i = m - 1; i >= 0; i--){
        int a = num1.charAt(i) - '0';
        for(int j = n - 1; j >= 0; j--){
            int b = num2.charAt(j) - '0';
            int sum = res[i + j + 1] + a * b;
            res[i + j] += sum / 10;            // 注意这里为 +=  否则会丢弃之前的运算结果 
            res[i + j + 1] = sum % 10;
        }
    }
    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < res.length; i++){
        if(i == 0 && res[i] == 0) continue;  //丢弃掉 首位的 0
        sb.append(res[i]);
    }
    return sb.toString();
   }

   2.幂指运算

你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出 leetcode 372

输入：a = 2, b = [4,3,3,8,5,2]
输出：100

递归性质 + 数学性质

1. (a*b)%k = (a%k)(b%k)%k
2. a^n % k = (a % k)^n % k

class Solution {
    int base = 1337;
    public int superPowCore(int a, int[] b,int idx) {
        if(idx == 0) return myPow(a,b[idx]);
        int powA = myPow(a,b[idx])  ;
        int powB = myPow(superPowCore(a,b,idx - 1),10);   // 缩小规模，递归调用
        return (powA * powB ) % base; // 每次乘法都要求模
    }
    public int myPow(int a, int b){
        if(b == 0) return 1;
        a %= base;        // 对因子求模
        if(b % 2 == 1){  // k 是奇数
            return (a * myPow(a,b - 1) ) % base; // 每次乘法都要求模
        }else{           // k 是偶数
            int half =  myPow(a, b / 2);
            return (half * half) % base;  // 每次乘法都要求模
        }
    }
}

3.阶乘末尾求0

给出一个非负整数K，问有多少个n，使得n!结果末尾有K个 0。 leetcode 793

求因子5的个数

1. 两个数相乘结果末尾有 0，一定是因为两个数中有因子 2 和 5，因为 10 = 2 x 5
2. 因为每个偶数都能分解出因子 2，因子 2 肯定比因子 5 多
3. 因此只需要求解因子5的个数，5的乘方阶可以分解出不只一个5

public int trailingZeroes(int m){
    int res = 0;
    int divider = 5;
    while(m >= divider){
        res += m / divider;
        divider *= 5;
    }
    return res;
}

二分技巧

1. 找到满足条件的最小数字，最大数字
2. 满足条件的个数为 最大 - 最小 + 1
3. 二分框架查找左边界与右边界

4. 结果要么为0 要么为5。 使用二分查找找出满足 zeta(x) = K 的最大 x 和最小 x。由于一定存在 zeta(5a-1) < zeta(5a) = zeta(5a+1) = zeta(5a+2) = zeta(5a+3) = zeta(5a+4) < zeta(5a+5) ```java public int preimageSizeFZF(int k) { long left = 0; long right = Long.MAX_VALUE;

   //左边界 while(left < right){

    long mid = left + (right - left) / 2;
    if(trailingZeroes(mid) < k){
        left = mid + 1;
    }else if(trailingZeroes(mid) > k){
        right = mid;
    }else{
        return 5;
    }

   }

   return 0;

}

long trailingZeroes(long n) { long res = 0; for (long d = n; d / 5 > 0; d = d / 5) { res += d / 5; } return res; }

<a name="hSDcL"></a>
### 4.平方根
---
[链接](https://www.yuque.com/kxuan42/leetcode/box56w) 二分
<a name="iH5QL"></a>
### 5.丑数
---
要生成第 n 个丑数，我们必须从第一个丑数 1 开始，向后逐渐的寻找。丑数只包含 2， 3，5 三个因子，所以生成方式就是在已经生成的丑数集合中乘以 [2, 3, 5] 而得到新的丑数。<br />现在的问题是在已经生成的丑数集合中，用哪个数字乘以 2？ 用哪个数字乘以 3？用哪个数字乘以 5？
很显然的一个结论：用还没乘过 2 的最小丑数乘以 2；用还没乘过 3 的最小丑数乘以 3；用还没乘过 5 的最小丑数乘以 5。然后在得到的数字中取最小，就是新的丑数。
```java
class Solution {
    public int getKthMagicNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        for(int i3 = 1, i5 = 1, i7 = 1, idx = 2; idx <= n; idx ++){
            int a = dp[i3] * 3;
            int b = dp[i5] * 5;
            int c = dp[i7] * 7;
            int res = Math.min(a,Math.min(b,c));
            dp[idx] = res;
            if(res == a) i3++;
            if(res == b) i5++;
            if(res == c) i7++;
        }
        return dp[n];
    }
}