算法

组合数公式：

$C_n^m=\frac{n!}{m!(n-m)!}$

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

质数判断方法：
若对于k，任意1<t<$\sqrt[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

代码

#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;
}

参考自链接

最后

以上就是完美小蝴蝶为你收集整理的大数 组合数C(n,m)算法算法代码的全部内容，希望文章能够帮你解决大数 组合数C(n,m)算法算法代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。