当前位置：首页 > news >正文

算法竞赛备考冲刺必刷题（C++） | AcWing 888 求组合数 IV

news 2026/5/12 22:20:03

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AcWing：888. 求组合数 IV - AcWing题库

【题目描述】

输入a , b a,ba,b，求C a b C_a^bCab的值。

注意结果可能很大，需要使用高精度计算。

【输入】

共一行，包含两个整数a aa和b bb。

【输出】

共一行，输出C a b C_a^bCab的值。

【输入样例】

5 3

【输出样例】

【算法标签】

《AcWing 888 求组合数IV》 #组合数学# #组合计数# #高精度#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=5005;// 质数表大小intprimes[N],cnt;// primes存储质数，cnt是质数个数boolst[N];// 筛法标记数组intsum[N];// 存储每个质因子的指数// 线性筛法求1~n的所有质数voidget_primes(intn){for(inti=2;i<=n;i++){if(!st[i])// 如果i是质数{primes[cnt++]=i;// 加入质数表}// 用当前已得到的质数筛掉合数for(intj=0;primes[j]<=n/i;j++){st[primes[j]*i]=true;// 标记合数if(i%primes[j]==0)// 如果primes[j]是i的最小质因数{break;// 保证每个合数只被最小的质因数筛掉}}}}// 计算n!中质因子p的指数（勒让德定理）intget(intn,intp){intres=0;// 指数结果// 勒让德公式：n!中质因子p的指数 = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ...while(n){res+=n/p;// 计算⌊n/p⌋n/=p;// 继续计算下一项}returnres;}// 高精度乘法：大整数A乘以小整数bvector<int>mul(vector<int>&A,intb){vector<int>C;// 存储结果intt=0;// 进位for(inti=0;i<A.size()||t;i++)// 遍历A的每一位或还有进位{if(i<A.size())// 如果A还有位数{t+=A[i]*b;// 当前位乘以b加上进位}C.push_back(t%10);// 取个位t/=10;// 计算进位}// 去掉前导0，但保留最后一位0（如果结果就是0）while(C.size()>1&&C.back()==0){C.pop_back();}returnC;}intmain(){inta,b;// 输入C(a, b)cin>>a>>b;// 1. 筛出1~a的所有质数get_primes(a);// 2. 计算组合数C(a,b)的质因数分解for(inti=0;i<cnt;i++){intp=primes[i];// 当前质数// 勒让德公式计算C(a,b)中质因子p的指数// C(a,b) = a! / (b! * (a-b)!)// 指数 = 在a!中的指数 - 在b!中的指数 - 在(a-b)!中的指数sum[i]=get(a,p)-get(b,p)-get(a-b,p);}// 3. 用高精度乘法计算结果vector<int>res;// 存储高精度结果，低位在前res.push_back(1);// 初始化为1// 遍历所有质因子for(inti=0;i<cnt;i++){intp=primes[i];// 当前质数intexp=sum[i];// 质因子p的指数// 将p乘exp次for(intj=0;j<exp;j++){res=mul(res,p);}}// 4. 输出结果（从高位到低位）for(inti=res.size()-1;i>=0;i--){cout<<res[i];}cout<<endl;return0;}