J - Judge(快速幂)(同余定理)
快速 定理
2023-09-11 14:22:48 时间
Description
Ocean从影视城回来后,吃了一个放大果实(恶魔果实的一种),高呼:“海贼王に、俺はなる!”
但是哪有这么好的事情?
物品的价值是有限度的,姑且认为物品的价值上界为$M$。
如果经过放大后物品的价值大于或者等于$M$,那么该物品价值将恒定以$M$的值减少,直到小于$M$为止。
比如价值为$19,M = 6$:要减少$3$次$M$,即$19 - 6 = 13,13 - 6 = 7,7 - 6 = 1 < 6。$
假设物品初始的价值为$1$,Ocean会对该物品使用$N$次能力。
他想知道经过$N$次放大之后,物品的价值是否大于$Y$?
Input
第一行输入一个整数$T$,代表有$T$组测试数据。
每组数据依次输入四个整数$x,N,M,Y,$分别代表上面提到的信息。
注:$1 <= T <= 100000,1 <= x, N <= 10^9,1 <= M <= 10^9,|Y| <= 2 * 10^9。$
每组数据依次输入四个整数$x,N,M,Y,$分别代表上面提到的信息。
注:$1 <= T <= 100000,1 <= x, N <= 10^9,1 <= M <= 10^9,|Y| <= 2 * 10^9。$
Output
若最后物品的价值大于$Y$请输出"YES",反之输出"NO"。(输出结果不带引号)
Sample Input
2 2 3 5 4 3 10 7 3
Sample Output
NO YES
Hint
对第一组测试数据,
第一次放大后物品价值为$2,2 < 5,$不减少。
第二次放大后物品价值为$4,4 < 5,$不减少。
第三次放大后物品价值为$8,8 > 5,$每次减少$5$,则$8 - 5 = 3 < 5$合法。
最后价值为$3,3 < 4。$
真的不懂当时自己明明知道方法,但是就是提交不上去,还是自己的基础知识没有掌握好。同余定理没有掌握好。
1 #include<stdio.h> 2 3 int main() 4 { 5 int T; 6 scanf("%d",&T); 7 while(T--) 8 { 9 long long t,x; 10 int n,m,y; 11 t=1; 12 scanf("%lld%d%d%d",&x,&n,&m,&y); 13 while(n!=0) 14 { 15 if(n%2) //这里的快速幂知识,和我记的模板并不一样,他是 16 t=(t*x)%m; //经过了自己的理解了的模板,我现在还没有到这一步 17 x=(x*x)%m; 18 n=n/2; //用到了同余定理 19 } 20 if(t>y) printf("YES\n"); 21 else printf("NO\n"); 22 } 23 return 0; 24 }
同余定理的另一种表述方式
如果经过放大后物品的价值大于或者等于$M$,那么该物品价值将恒定以$M$的值减少,直到小于$M$为止。
比如价值为$19,M = 6$:要减少$3$次$M$,即$19 - 6 = 13,13 - 6 = 7,7 - 6 = 1 < 6。$
相关文章
- hdu5015 矩阵快速幂233(好题)
- 【HDU4471】Homework(矩阵快速幂)
- 【BZOJ2875】【NOI2012】随机数生成器(矩阵快速幂)
- Google Earth Engine(GEE)——农田的快速分类
- 《KAFKA官方文档》第三章:快速入门(二)
- ThinkPHP3.1快速入门(12)自动验证
- excel 如何快速实现绝对引用
- Android 14 新功能之 HighLights:快速实现文本高亮~
- Redis快速入门
- 【数字IC验证快速入门】20、SystemVerilog学习之基本语法7(覆盖率驱动...内含实践练习)
- 【校招Verilog快速入门】时序逻辑篇:VL22、根据状态转移图实现时序电路(FSM)
- 【ESWIN编程大赛】一、熟悉PINT环境,借助向量相加demo快速上手