AcWing - 求组合数 IV(分解质因数)
发布日期:2021-07-01 00:21:42
浏览次数:4
分类:技术文章
本文共 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月18日 11时24分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
Apache Kafka:优化部署的 10 种最佳实践
2019-05-01
Leetcode 35. 搜索插入位置 c#
2019-05-01
LeetCode62. 不同路径
2019-05-01
记gdb调试一次报错:Missing separate debuginfos, use: zypper install glibc-32bit-debuginfo-2.22-15.3.x86_64
2019-05-01
LeetCode242. 有效的字母异位词
2019-05-01
LeetCode83. 删除排序链表中的重复元素
2019-05-01
关于301和302重定向的理解
2019-05-01
使用java代码和jmeter脚本批量造数
2019-05-01
[9] JMeter-常用函数的使用
2019-05-01
[10] JMeter-察看结果树,你知道都有哪些功能吗?
2019-05-01
[11] JMeter-结果分析之聚合报告
2019-05-01
[12] JMeter-结果分析之图形图表
2019-05-01
[13] JMeter-详解JMeter参数化之CSV Data Set Config
2019-05-01
[14] JMeter关联-详解JMeter正则表达式提取器
2019-05-01
优化jmeter脚本
2019-05-01
Gradle基础使用总结1
2019-05-01
性能测试场景设置---不同场景下对应的jmeter脚本【不定时补充】
2019-05-01
登录oracle数据库时常用的操作命令整理
2019-05-01