题目描述计算从N NN个物品中取M MM个的组合数C ( N , M ) N ! ( N − M ) ! × M ! C(N, M) \frac{N!}{(N-M)! \times M!}C(N,M)(N−M)!×M!N!的精确值。输入格式输入包含一行或多行每行包含两个整数N NN和M MM5 ≤ N ≤ 100 5 \leq N \leq 1005≤N≤1005 ≤ M ≤ 100 5 \leq M \leq 1005≤M≤100M ≤ N M \leq NM≤N。最后一行以0 0结束。输出格式对于每对( N , M ) (N, M)(N,M)输出N things taken M at a time is C exactly.样例输入100 6 20 5 18 6 0 0样例输出100 things taken 6 at a time is 1192052400 exactly. 20 things taken 5 at a time is 15504 exactly. 18 things taken 6 at a time is 18564 exactly.题目分析问题的本质这是一个组合数计算问题。需要精确计算C ( N , M ) C(N, M)C(N,M)其中N , M ≤ 100 N, M \leq 100N,M≤100。直接计算的挑战直接计算阶乘N ! N!N!会导致数字非常巨大100 ! 100!100!有158 158158位但最终结果C ( N , M ) C(N, M)C(N,M)在32 3232位整数范围内。因此需要一种方法避免中间结果溢出。解决思路使用质因数分解法将C ( N , M ) C(N, M)C(N,M)表示为质因数的乘积形式计算分子和分母中每个质数的指数相减得到最终指数计算乘积质因数分解的优势中间结果不会溢出因为最终结果在32 3232位范围内但中间乘积可能超过使用大整数或边乘边除可避免溢出但质因数分解更直观参考代码// Combinations// UVa ID: 369// Verdict: Accepted// Submission Date: 2016-06-25// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 100 以内的质数vectorintprimes{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};// 计算 n! 的质因数分解结果存储在 factors 映射中voidgetPrimes(intn,mapint,intfactors){for(inti2;in;i){intti;// 对每个数进行质因数分解for(autop:primes){while(t%p0){factors[p];t/p;}}}}intmain(intargc,char*argv[]){intN,M;while(cinNM,NM){mapint,intfactorsOfN;// N! 的质因数mapint,intfactorsOfN_M;// (N-M)! 的质因数mapint,intfactorsOfM;// M! 的质因数// 初始化for(autop:primes){factorsOfN[p]0;factorsOfN_M[p]0;factorsOfM[p]0;}// 计算各个阶乘的质因数分解getPrimes(N,factorsOfN);getPrimes(N-M,factorsOfN_M);getPrimes(M,factorsOfM);// C(N,M) N! / ((N-M)! * M!)// 减去分母的质因数for(autop:factorsOfN_M)if(p.second0)factorsOfN[p.first]-factorsOfN_M[p.first];for(autop:factorsOfM)if(p.second0)factorsOfN[p.first]-factorsOfM[p.first];// 计算最终乘积longlongproduct1;for(autop:factorsOfN)if(p.second0)product*pow(p.first,p.second);coutN things taken M at a time is ;coutproduct exactly.endl;}return0;}
UVa 369 Combinations
题目描述计算从N NN个物品中取M MM个的组合数C ( N , M ) N ! ( N − M ) ! × M ! C(N, M) \frac{N!}{(N-M)! \times M!}C(N,M)(N−M)!×M!N!的精确值。输入格式输入包含一行或多行每行包含两个整数N NN和M MM5 ≤ N ≤ 100 5 \leq N \leq 1005≤N≤1005 ≤ M ≤ 100 5 \leq M \leq 1005≤M≤100M ≤ N M \leq NM≤N。最后一行以0 0结束。输出格式对于每对( N , M ) (N, M)(N,M)输出N things taken M at a time is C exactly.样例输入100 6 20 5 18 6 0 0样例输出100 things taken 6 at a time is 1192052400 exactly. 20 things taken 5 at a time is 15504 exactly. 18 things taken 6 at a time is 18564 exactly.题目分析问题的本质这是一个组合数计算问题。需要精确计算C ( N , M ) C(N, M)C(N,M)其中N , M ≤ 100 N, M \leq 100N,M≤100。直接计算的挑战直接计算阶乘N ! N!N!会导致数字非常巨大100 ! 100!100!有158 158158位但最终结果C ( N , M ) C(N, M)C(N,M)在32 3232位整数范围内。因此需要一种方法避免中间结果溢出。解决思路使用质因数分解法将C ( N , M ) C(N, M)C(N,M)表示为质因数的乘积形式计算分子和分母中每个质数的指数相减得到最终指数计算乘积质因数分解的优势中间结果不会溢出因为最终结果在32 3232位范围内但中间乘积可能超过使用大整数或边乘边除可避免溢出但质因数分解更直观参考代码// Combinations// UVa ID: 369// Verdict: Accepted// Submission Date: 2016-06-25// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 100 以内的质数vectorintprimes{2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};// 计算 n! 的质因数分解结果存储在 factors 映射中voidgetPrimes(intn,mapint,intfactors){for(inti2;in;i){intti;// 对每个数进行质因数分解for(autop:primes){while(t%p0){factors[p];t/p;}}}}intmain(intargc,char*argv[]){intN,M;while(cinNM,NM){mapint,intfactorsOfN;// N! 的质因数mapint,intfactorsOfN_M;// (N-M)! 的质因数mapint,intfactorsOfM;// M! 的质因数// 初始化for(autop:primes){factorsOfN[p]0;factorsOfN_M[p]0;factorsOfM[p]0;}// 计算各个阶乘的质因数分解getPrimes(N,factorsOfN);getPrimes(N-M,factorsOfN_M);getPrimes(M,factorsOfM);// C(N,M) N! / ((N-M)! * M!)// 减去分母的质因数for(autop:factorsOfN_M)if(p.second0)factorsOfN[p.first]-factorsOfN_M[p.first];for(autop:factorsOfM)if(p.second0)factorsOfN[p.first]-factorsOfM[p.first];// 计算最终乘积longlongproduct1;for(autop:factorsOfN)if(p.second0)product*pow(p.first,p.second);coutN things taken M at a time is ;coutproduct exactly.endl;}return0;}
