| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
就是一个求组合数,只要在乘的时候约一下分就可以了,为确保不越界,我开的都是long long#include<cstdio>
#pragma warning (disable:4996)
using namespace std;
long long gcd(long long x, long long y) //求解x,y的最大公约数
{
return y == 0 ? x : gcd(y, x%y);
}
long long factorial(long long n, long long m) //从n个中选取m个,总共有多少中方案,利用公式(n*(n-1)*...*(n-m+1))/(m!)
{
if (m == 0 || n == 0)
return 1;
m = (n - m) > m ? m : n - m; //求组合数公式化简,(n,m)=(n,n-m),我们算累乘次数小的那个
long long morther, son, result,count; //分母,分子,以及最终结果,累乘的次数
morther = 1; son = n - m + 1;
result = 1; count = 1; //分母从1乘到m,分子从n-m+1乘到n,分子和分母乘数个数都是m
while (count <= m) //循环的条件是累乘count次
{
long long temp; //即将乘入分子与分母的最大公约数
temp = gcd(son, morther);
result = result * (son / temp) / (morther / temp); //分子、分母同时除以最大公约数,然后先乘后除(不可先除后乘法,以免出现0)
son++; //分子分母同时向上累加一个,计数器加1
morther++;
count++;
}
return result;
}
int main()
{
int n, m;
while (scanf("%d %d", &n, &m) != EOF)
{
if (n == 0 && m == 0)
return 0;
else
printf("%lld\n", factorial(n, m));
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator