4. 高精度求组合数

888. 求组合数 IV
输入 a,b，求 的值。
注意结果可能很大，需要使用高精度计算。
输入格式
共一行，包含两个整数 a 和 b。
输出格式
共一行，输出 的值。
数据范围
1≤b≤a≤5000
输入样例：

5 3

输出样例：

10

要素

• 一组数据
• 1≤b≤a≤5000
• 没有取模要求

结果可能很大，用高精度乘法和高精度除法做运算

问题来了，能不能只用乘法？
是可以的，将a和b都用算术基本定理分解为质因数的乘积，消去公共质因子后剩余的就只有乘法了。

求 a! 的分解质因数的结果

a! = x0``p0`` * x1``p1`` * ... * xk``pk
对于其中一个质因子x如何求它的次数？
cnt(x) = a // x + a//x``2`` + a//x``3`` + ...

//求num! 分解质因子x 的次数
    static int get(int num, int x) {
        int ans = 0;
        while (num > 0) {
            ans += num / x;
            num /= x;
        }
        return ans;
    }

import java.util.*;
public class Main {
    static final int N = 5010;
    static int idx;
    static int[] primers = new int[N];
    static boolean[] st = new boolean[N + 1];
    static int[] sum = new int[N + 1];
    static {
        //预处理下1-N的所有质数
        for (int i = 2; i <= N; i++) {
            if (!st[i]) primers[idx++] = i;
            for (int j = 0; primers[j] <= N / i; j++) {
                st[primers[j] * i] = true;
                if (i % primers[j] == 0) break;
            }
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();
        for (int i = 0; i < idx; i++) {
            sum[i] += get(a, primers[i]) - get(b, primers[i]) - get(a - b, primers[i]);
        }
        // for (int i = 0; i < idx; i++) {
        //     System.out.println(primers[i] + " " + sum[i]);
        // }
        List<Integer> res = new ArrayList<>();
        res.add(1);
        for (int i = 0; i < idx; i++) {
            for (int j = 0; j < sum[i]; j++) {
                res = mul(res, primers[i]);
            }
        }
        for (int i = res.size() - 1; i >= 0; i--) {
            System.out.print(res.get(i));
        }
    }
    //求num! 分解质因子p 的次数
    static int get(int num, int p) {
        int ans = 0;
        while (num > 0) {
            ans += num / p;
            num /= p;
        }
        return ans;
    }
    //高精度乘法
    static List<Integer> mul(List<Integer> a, int b) {
        List<Integer> res = new ArrayList<>();
        int t = 0;
        for (int i = 0; i < a.size(); i++) {
            t += a.get(i) * b;
            res.add(t % 10);
            t /= 10;
        }
        while (t > 0) {
            res.add(t % 10);
            t /= 10;
        }
        return res;
    }
}