Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

就是一个求组合数,只要在乘的时候约一下分就可以了,为确保不越界,我开的都是long long

Posted by 110120_119 at 2019-04-02 15:37:13 on Problem 2249
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator