Description

In how many ways can you choose k elements out of n elements, not taking order into account?

Write a program to compute this number.

Input

The input will contain one or more test cases.

Each test case consists of one line containing two integers n (n>=1) and k (0<=k<=n).

Input is terminated by two zeroes for n and k.

Output

For each test case, print one line containing the required number. This number will always fit into an integer, i.e. it will be less than 2

³¹.

Warning: Don't underestimate the problem. The result will fit into an integer - but if all intermediate results arising during the computation will also fit into an integer depends on your algorithm. The test cases will go to the limit.

Sample Input

4 210 549 60 0

Sample Output

625213983816

Source

解题思路：

本题题意很明确，就是让求C（n,m）是多少，但传统的组合公式计算过程中会越界，所以采用另一种思路，把组合公式的分子和分母的数字分别存到两个数组中，然后两层循环，分别求出分子和分母的最大公约数，然后约分，这样把分子分母化成最简。最后再采用传统的组合公式就可以了。

代码：

#include 
    
     using namespace std;const int maxn=3000;int up[maxn],down[maxn];//分别存分子和分母的数int gcd(int a,int b){    if(!a)        return b;    int c;    while(b)    {        c=b;        b=a%b;        a=c;    }    return a;}int main(){    int n,m;    while(cin>>n>>m&&(m||n))    {        if(m>n-m)            m=n-m;        int temp=n;        for(int i=1;i<=m;i++)//根据组合公式把原始的分子分母分别存在数组中        {            up[i]=temp--;            down[i]=i;        }        for(int i=1;i<=m;i++)//外层循环代表分母，对分母依次进行约分            for(int j=1;j<=m;j++)        {            temp=gcd(down[i],up[j]);            if(temp>1)            {                up[j]/=temp;                down[i]/=temp;            }            if(down[i]==1)//分母已经为1，退出，进行下一个分母的约分                break;        }        int mul=1;        for(int i=1;i<=m;i++)            mul=mul*up[i]/down[i];        cout<
     
      <