20.求组合数 IV

20.求组合数 IV

 这种求组合数问题是要把最终答案算出来,而不是把最终答案模上一个数

就是直接用定义求组合数,分解质因数,然后用上高精度乘法

还是要吐槽一句python自带高精,python大法好,之后还要转python,酸了酸了

如何求a!中有多少个质因子p呢

20.求组合数 IV

 一直乘到p的若干次方比a大了为止,这步操作时间复杂度是log p

思路:
1:先把1 ~ 5000内的质数筛出来

2:求每个质数的次数

3:用高精度乘法把所有质因子乘出来,算出结果

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int N = 5010;
 4 int primes[N], cnt;
 5 bool st[N];
 6 int sum[N];
 7 void get_primes(int n) {
 8     for (int i = 2; i <= n; i++) {
 9         if (!st[i]) {
10             primes[cnt++] = i;
11         }
12         for (int j = 0; primes[j] <= n / i; j++) {
13             st[primes[j] * i] = true;
14             if (i % primes[j] == 0) {
15                 break;
16             }
17         }
18     }
19 }
20 int get(int n, int p) { //求n!包含的p的次数
21     int res = 0;
22     while (n) {
23         res += n / p;
24         n /= p;
25     }
26     return res;
27 }
28 vector<int> mul(vector<int> &a, int b) {
29     vector<int> c;
30     int t = 0;
31     for (int i = 0; i < a.size(); i++) {
32         t += a[i] * b;
33         c.push_back(t % 10);
34         t /= 10;
35     }
36     while (t) {
37         c.push_back(t % 10);
38         t /= 10;
39     }
40     return c;
41 }
42 int main() {
43     int a, b;
44     cin >> a >> b;
45     get_primes(a); //1.筛选出所有质因子
46     for (int i = 0; i < cnt; i++) { //2.求出每一个质数的次数
47         int p = primes[i];
48         sum[i] = get(a, p) - get(b, p) - get(a - b, p);
49     }
50     //3.高精度乘法
51     vector<int> res;
52     res.push_back(1); //最开始是1
53     for (int i = 0; i < cnt; i++) { //枚举所有质因数
54         for (int j = 0; j < sum[i]; j++) { //这个质因数的次数
55             res = mul(res, primes[i]);
56         }
57     }
58     for (int i = res.size() - 1; i >= 0; i--) { //输出
59         cout << res[i];
60     }
61     cout << endl;
62     return 0;
63 }

 

上一篇:562. 背包问题 IV


下一篇:怎么区分PV、IV、UV