这种求组合数问题是要把最终答案算出来,而不是把最终答案模上一个数
就是直接用定义求组合数,分解质因数,然后用上高精度乘法
还是要吐槽一句python自带高精,python大法好,之后还要转python,酸了酸了
如何求a!中有多少个质因子p呢
一直乘到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 }