AcWing - 求组合数 IV(分解质因数)
发布日期:2021-07-01 00:21:42
浏览次数:3
分类:技术文章
本文共 1706 字,大约阅读时间需要 5 分钟。
题目链接:
时/空限制:1s / 64MB题目描述
输入a,b,求的值。
注意结果可能很大,需要使用高精度计算。
输入格式
共一行,包含两个整数a和b。
输出格式
共一行,输出Cab的值。
数据范围
1≤b≤a≤5000
输入样例
5 3
输出样例
10
解题思路
题意:求的值
思路:当我们需要求出组合数的真实值,而非对某个数的余数时,分解质因数的方式比较好用:
假设A = p^a1*p^a2*...*p^ak,B = p^b1*p^b2*...*p^bk,则A/B = p^(a1-b1)*p^(a2-b2)*...*p^(ak-bk)。1. 筛法求出范围内的所有质数。
2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ... 3. 用高精度乘法将所有质因子相乘。Accepted Code:
/* * @Author: lzyws739307453 * @Language: C++ */#includeusing namespace std;typedef long long ll;const int MAXN = 5005;bool isp[MAXN];int cnt = 0;int pre[MAXN], rat[MAXN];void prime(int n) { for (int i = 2; i <= n; i++) { if (!isp[i]) pre[cnt++] = i; for (int j = 0; j < cnt && pre[j] <= n / i; j++) { isp[i * pre[j]] = true; if (!(i % pre[j])) break; } }}int rate(int n, int p) { int res = 0; while (n) { res += n / p; n /= p; } return res;}vector Mul(vector a, int b) { vector p; int t = 0; for (int i = 0; i < a.size(); i++) { t += a[i] * b; p.push_back(t % 10); t /= 10; } while (t) { p.push_back(t % 10); t /= 10; } return p;}int main() { int a, b; scanf("%d%d", &a, &b); prime(a); for (int i = 0; i < cnt; i++) { int p = pre[i]; rat[i] = rate(a, p) - rate(b, p) - rate(a - b, p); } vector res; res.push_back(1); for (int i = 0; i < cnt; i++) { for (int j = 0; j < rat[i]; j++) res = Mul(res, pre[i]); } for (int i = res.size() - 1; ~i; i--) printf("%d", res[i]); printf("\n"); return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/99715833 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过按个爪印,很不错,赞一个!
[***.219.124.196]2024年04月27日 06时49分25秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Ubuntu更新后终端中字体的颜色全是白色
2019-04-30
vscode git
2019-04-30
基于MATLAB的二进制数字调制与解调信号的仿真——2PSK
2019-04-30
基于MATLAB的模拟调制信号与解调的仿真——DSB
2019-04-30
HDU - 1166 敌兵布阵 (树状数组模板题/线段树模板题)
2019-04-30
CodeForces - 456C Boredom (dp)
2019-04-30
CodeForces - 675A Infinite Sequence(简单数论 细节)
2019-04-30
CodeForces - 1042B Vitamins (思维)
2019-04-30
ACM 2013 长沙区域赛 Collision (几何)
2019-04-30
ACM 2014 鞍山区域赛 E - Hatsune Miku (dp)
2019-04-30
反向传播&梯度下降 的直观理解程序(numpy)
2019-04-30
CodeForces - 931B World Cup (思维 模拟)
2019-04-30
ACM 2017 北京区域赛 J-Pangu and Stones(区间dp)
2019-04-30
java常用类 String面试题
2019-04-30
利用ffmpeg合并音频和视频
2019-04-30
select下拉框分组展示插件的使用--(select-mania插件的使用)
2019-04-30
Java Lambda表达式的应用--Stream API操作集合框架
2019-04-30
Myslq连接(JDBC)url属性的参数的设置
2019-04-30