B - 组合数的计算【C++】

来杯Sherry

发布于 2023-05-25 06:14:37

29500

代码可运行

文章被收录于专栏：第一专栏第一专栏

运行总次数：0

代码可运行

B - 组合数的计算【C++】

Description

给定n组整数(a,b)，计算组合数C(a,b)的值。如C(3,1)=3,C(4,2)=6。

Input

第一行为一个整数n，表示有多少组测试数据。(n <= 100000) 第2-n+1行，每行两个整数分别代表a,b；中间用空格隔开。(a,b <= 40)

Output

对于每组输入，输出其组合数的值。每个输出占一行。

Sample

Input

Output

Tip

long long 直接开15次左右阶乘就会爆，double 会出现精度问题

公式

C(n,m)=n!/((n-m)!*m!)（m≤n）

代码

#include<bits/stdc++.h>

using namespace std;

void C(int a,int b)//4 2
{
    long long int  res = 1;
    //long long int x =1,y =1;
    if(a == b || b == 0)res = 1;
    else if(a < b)res = 0;//最容易遗漏，因此wa了好几次
    else if(b == 1 || a-b == 1)res = a;
    else
    {
        int j =1;
        for(int i = a-b+1; i <= a; i++)//接都是阶乘，时间浪费,这里折中一下
            {
                res *= i;
                if(res%j == 0 || j <= b)
                {
                    res /= j;
                    j++;
                }
            }

//        cout<<x<<" "<<y<<endl;
//       res = x;
    }
    cout<<res<<endl;
//    cout<<res<<endl;
}
int main()
{
    int n;
    cin>>n;
    int a,b;
    while(n--)
    {
        cin>>a>>b;
        C(a,b);
    }
}