本文共 1706 字，大约阅读时间需要 5 分钟。

题目链接:

时/空限制：1s / 64MB

题目描述

输入a,b，求的值。

注意结果可能很大，需要使用高精度计算。

输入格式

共一行，包含两个整数a和b。

输出格式

共一行，输出Cab的值。

数据范围

1≤b≤a≤5000

输入样例

5 3

输出样例

10

解题思路

题意:求的值

思路:当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：

假设A = p^a1*p^a2*...*p^ak，B = p^b1*p^b2*...*p^bk，则A/B = p^(a1-b1)*p^(a2-b2)*...*p^(ak-bk)。

    1. 筛法求出范围内的所有质数。

    2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。        n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...     3. 用高精度乘法将所有质因子相乘。

Accepted Code:

/*  * @Author: lzyws739307453  * @Language: C++  */#include 
   
    using namespace std;typedef long long ll;const int MAXN = 5005;bool isp[MAXN];int cnt = 0;int pre[MAXN], rat[MAXN];void prime(int n) {    for (int i = 2; i <= n; i++) {        if (!isp[i])            pre[cnt++] = i;        for (int j = 0; j < cnt && pre[j] <= n / i; j++) {            isp[i * pre[j]] = true;            if (!(i % pre[j]))                break;        }    }}int rate(int n, int p) {    int res = 0;    while (n) {        res += n / p;        n /= p;    }    return res;}vector 
    
      Mul(vector 
     
       a, int b) {    vector 
      
        p;    int t = 0;    for (int i = 0; i < a.size(); i++) {        t += a[i] * b;        p.push_back(t % 10);        t /= 10;    }    while (t) {        p.push_back(t % 10);        t /= 10;    }    return p;}int main() {    int a, b;    scanf("%d%d", &a, &b);    prime(a);    for (int i = 0; i < cnt; i++) {        int p = pre[i];        rat[i] = rate(a, p) - rate(b, p) - rate(a - b, p);    }    vector 
       
         res;    res.push_back(1);    for (int i = 0; i < cnt; i++) {        for (int j = 0; j < rat[i]; j++)            res = Mul(res, pre[i]);    }    for (int i = res.size() - 1; ~i; i--)        printf("%d", res[i]);    printf("\n");    return 0;}
       
      
     
    
   

转载地址：http://gubtf.baihongyu.com/