AcWing - 求组合数 III(lucas&逆元)
发布日期:2021-07-01 00:21:42
浏览次数:3
分类:技术文章
本文共 1177 字,大约阅读时间需要 3 分钟。
题目链接:
时/空限制:1s / 64MB题目描述
给定n组询问,每组询问给定三个整数a,b,p,其中p是质数,请你输出的值。
输入格式
第一行包含整数n。
接下来n行,每行包含一组a,b,p。
输出格式
共n行,每行输出一个询问的解。
数据范围
1≤n≤20,
1≤b≤a≤10^18, 1≤p≤10^5,
输入样例
3
5 3 7 3 1 5 6 4 13
输出样例
3
3 2
解题思路
题意:求的值。
思路:- 100000组, 1 <= b <= a <= 2000, 递推 -> O(N^2).
- 10000组, 1 <= b <= a <= 10^5, 预处理 -> O(NlogN).
- 20组, 1 <= b <= a <= 10^18, p <= 10^5, 卢卡斯定理(lucas)
Accepted Code:
/* * @Author: lzyws739307453 * @Language: C++ */#includeusing namespace std;typedef long long ll;int Fast_Power(int a, int b, int p) { int res = 1; while (b) { if (b & 1) res = 1ll * res * a % p; a = 1ll * a * a % p; b >>= 1; } return res;}int Com_Num(int a, int b, int p) { int res = 1; for (int i = 1, j = a; i <= b; i++, j--) res = 1ll * res * j % p * Fast_Power(i, p - 2, p) % p; return res;}int lucas(ll a, ll b, int p) { if (a < p && b < p) return Com_Num(a, b, p); return 1ll * Com_Num(a % p, b % p, p) * lucas(a / p, b / p, p) % p;}int main() { int t; scanf("%d", &t); while (t--) { int p; ll a, b; scanf("%lld%lld%d", &a, &b, &p); printf("%d\n", lucas(a, b, p)); } return 0;}
转载地址:https://lzyws739307453.blog.csdn.net/article/details/99713778 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
初次前来,多多关照!
[***.217.46.12]2024年04月15日 04时56分21秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
golang实现大数据量文件的排序
2019-04-30
golang中的time包
2019-04-30
2019NOIP D4题 加工领奖
2019-04-30
2021.5.19 JS高级第二天
2019-04-30
SpringBoot内置Tomcat配置参数
2019-04-30
linux 根目录下文件夹分析
2019-04-30
linux 查看分区和文件大小
2019-04-30
技术转管理?这些“坑”你要绕道走
2019-04-30
领域驱动设计(DDD)前夜:面向对象思想
2019-04-30
Camera驱动调试小记
2019-04-30
四线触摸屏原理
2019-04-30
C/C++如何返回一个数组/指针
2019-04-30
腾讯AI语音识别API踩坑记录
2019-04-30
安装openrave 0.9的各种依赖包
2019-05-01
@FeignClient注解的重复名称解决
2019-05-01
java.net.BindException: 无法指定被请求的地址
2019-05-01
scala list
2019-05-01
svn服务器安装
2019-05-01
spark 笔记1
2019-05-01
shell dirname basename
2019-05-01