求组合数 AcWing 888. 求组合数 IV

旧城等待， 2023-09-28 13:22 83阅读 0赞

## 求组合数 AcWing 888. 求组合数 IV ##

### 原题链接 ###

[AcWing 888. 求组合数 IV][AcWing 888. _ IV]

### 算法标签 ###

组合数学 组合计数 高精度

### 思路 ###

![在这里插入图片描述][ed50292a50dc4a7a8602798b5b074892.png]

![··][cf74014724884acdbfdb3791e78084b3.png]

### 代码 ###

#include<bits/stdc++.h>
    #define int long long
    #define abs fabs
    #define rep(i, a, b) for(int i=a;i<b;++i)
    #define Rep(i, a, b) for(int i=a;i>=b;--i)
    using namespace std;
    const int N = 5015;
    int pr[N], st[N], s[N], cnt;
    inline int read(){
       int s=0,w=1;
       char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
       while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
       return s*w;
    }
    void put(int x) {
        if(x<0) putchar('-'),x=-x;
        if(x>=10) put(x/10);
        putchar(x%10^48);
    }
    void pri(int n){
        rep(i, 2, n+1){
            if(!st[i]){
                pr[cnt++]=i;
            }
            for(int j=0; pr[j]<=n/i; ++j){
                st[pr[j]*i]=true;
                if(!(i%pr[j])){
                    break;
                }
            }
        }
    }
    int get(int n, int p){
        int res=0;
        while(n){
            res+=n/p;
            n/=p;
        }
        return res;
    }
    vector<int> mul(vector<int> a, int b){
        vector<int> c;
        int t=0;
        rep(i, 0, a.size()){
            t+=a[i]*b;
            c.push_back(t%10);
            t/=10;
        }
        while(t){
            c.push_back(t%10);
            t/=10;
        }
        return c;
    }
    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        int a=read(), b=read();
        pri(a);
        rep(i, 0, cnt){
            int p=pr[i];
            s[i]=get(a, p)-get(a-b, p)-get(b, p);
        }
        vector<int> res;
        res.push_back(1);
        rep(i, 0, cnt){
            rep(j, 0, s[i]){
                res=mul(res, pr[i]);
            }
        }
        Rep(i, res.size()-1, 0){
            printf("%lld", res[i]);
        }
    }

原创不易  
转载请标明出处  
如果对你有所帮助 别忘啦点赞支持哈  
![在这里插入图片描述][9cb4cb80a18345158f8a69e2f196e5b9.png]

[AcWing 888. _ IV]: https://www.acwing.com/problem/content/890/
[ed50292a50dc4a7a8602798b5b074892.png]: https://img-blog.csdnimg.cn/ed50292a50dc4a7a8602798b5b074892.png
[cf74014724884acdbfdb3791e78084b3.png]: https://img-blog.csdnimg.cn/cf74014724884acdbfdb3791e78084b3.png
[9cb4cb80a18345158f8a69e2f196e5b9.png]: https://img-blog.csdnimg.cn/9cb4cb80a18345158f8a69e2f196e5b9.png