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