大数组合数C(n,m)算法算法代码

63 阅读 0 评论 42 点赞

我是靠谱客的博主完美小蝴蝶，这篇文章主要介绍大数组合数C(n,m)算法算法代码，现在分享给大家，希望可以做个参考。

算法

组合数公式：

$C^m_n=frac{n!}{m!(n-m)!}$

鉴于n，m较大时结果将超出int范围，算法如下：
分别对各阶乘进行质因数分解，计算各个质因数的次数，分别约分后在进行计算

质数判断方法：
若对于k，任意1<t< $2 k$ ，若k不能整除t，则k为质数

质因数分解方法：
对于质数k<n，n、(n-1)、(n-2)…1中能整除k的数应有n/k个，若n/k>k，则将出现能整除k²的数，个数应为(n/k)/k，以此类推，n!中质数k的次数应为n/k+(n/k)/k+…，加到商小于k

代码

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<iostream>
#include<vector>
using namespace std;
//组合数C(n,m)的计算函数
//算法：C(n,m)=n!/(m!*(n-m)!)
//对各阶乘进行质因数分解，通过计算各质因数的次数并作约分得到最后的结果
//计算n以下的质因数
vector<int> nPrime(int n) {
int k = 2;
vector<int> v;
while (k <= n) {
bool isPrime = true;
int t = sqrt(k);
for (; t > 1; t--) {
if (k%t == 0) {
isPrime = false;
break;
}
}
if (isPrime)
v.push_back(k);
k++;
}
return v;
}
//计算n!中素数m的次数
int dPrime(int n, int m) {
int pow = 0;
while (n >= m) {
int temp = n / m;
pow += temp;
n = temp;
}
return pow;
}
//计算组合数C(n,m)
int C(int n, int m) {
long long ans = 1;
vector<int> v = nPrime(n);
for (int i = 0; i < v.size(); i++) {
int k = v.at(i),pow;
pow = dPrime(n, k) - dPrime(m, k) - dPrime(n - m, k);
for (int j = 0; j < pow; j++) {
ans *= k;
ans %= (int)(1e9 + 7);
}
}
return (int)ans;
}
int main() {
int n, m;
while (cin >> n >> m) {
cout << C(n, m) << endl;
}
return 0;
}