AcWing 888 求组合数 IV 题解 （求组合数）

本文主要是介绍AcWing 888 求组合数 IV 题解 （求组合数），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

思路：先算出小于a的所有质数，再得出a、b、（a - b）的阶乘中包含的质数的次数，用get(a) - get(b) - get(a - b)即得出组合数中包含的各个质数的次数，然后利用大整数乘法，将这些质数（带次数）乘积算出来，即得结果

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 5010;

int prime[N], cnt;//记录质数和质数的个数
bool st[N];//记录一个数是不是质数
int sum[N];//记录一个质数在组合数中的次数

void get_prime(int n){//欧拉筛
    for(int i = 2; i <= n; i ++ ){
        if(!st[i]){
            st[i] = true;
            prime[cnt ++ ] = i;
        }
        for(int j = 0; j < cnt && prime[j] * i <= n; j ++ ){
            st[prime[j] * i] = true;
            if(i % prime[j] == 0) break;
        }
    }
}

int get(int a, int p){//计算a的阶乘中，质数p的次数，记模板
    int res = 0;
    while(a){
        res += a / p;
        a /= p;
    }
    return res;
}

vector<int> mul(vector<int> a, int b){//高精度乘法
    vector<int>c;
    int t = 0;//记录进位
    for(int i = 0 ; i < a.size(); i ++ ){
        t += a[i] * b;
        c.push_back(t % 10);
        t /= 10;
    }
    while(t){
        c.push_back(t % 10);
        t /= 10;
    }
    return c;
}

int main()
{
    int a, b;
    cin>>a>>b;
    
    get_prime(a);//算出小于a的所有质数并记录
    
    for(int i = 0; i < cnt; i ++ ){
        int p = prime[i];
        sum[i] = get(a, p) - get(b, p) - get(a - b, p);//记录组合数中含有某个质数的次数 
    } 
    
    vector<int> res;
    res.push_back(1);//利用vector储存大整数乘法的结果
    
    for(int i = 0; i < cnt; i ++ ){
        for(int j = 0; j < sum[i]; j ++ ){
          res = mul(res, prime[i]);//累乘得答案 
        }
    }
    
    for(int i = res.size() - 1; i >= 0; i -- ){
        cout<<res[i];
    }
    return 0;
}

这篇关于AcWing 888 求组合数 IV 题解 （求组合数）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！