当前位置: 代码迷 >> 综合 >> hpuoj 1194: Judge
  详细解决方案

hpuoj 1194: Judge

热度:40   发布时间:2023-11-26 10:03:19.0

点击打开链接

1194: Judge [快速幂]

时间限制: 1 Sec  内存限制: 128 MB

提交: 1250  解决: 168  统计

题目描述

Ocean从影视城回来后,吃了一个放大果实(恶魔果实的一种),高呼:“海贼王に、俺はなる!

Ocean每使用一次能力,就可以将一个物品的价值放大xx倍(原价值乘以xx)。
但是哪有这么好的事情?
物品的价值是有限度的,姑且认为物品的价值上界为MM
如果经过放大后物品的价值大于或者等于MM,那么该物品价值将恒定以MM的值减少,直到小于MM为止。
比如价值为19M=619,M=6:要减少33MM,即19?6=1313?6=77?6=1<619?6=13,13?6=7,7?6=1<6。

假设物品初始的价值为11,Ocean会对该物品使用NN次能力。
他想知道经过NN次放大之后,物品的价值是否大于YY

输入

第一行输入一个整数TT,代表有TT组测试数据。
每组数据依次输入四个整数xNMYx,N,M,Y,分别代表上面提到的信息。

注:1<=T<=1000001<=x,N<=1091<=M<=109|Y|<=2?1091<=T<=100000,1<=x,N<=109,1<=M<=109,|Y|<=2?109。

输出

若最后物品的价值大于YY请输出"YES",反之输出"NO"。(输出结果不带引号)

样例输入

2
2 3 5 4
3 10 7 3

样例输出

NO
YES

提示

对第一组测试数据,
第一次放大后物品价值为22<52,2<5,不减少。
第二次放大后物品价值为44<54,4<5,不减少。
第三次放大后物品价值为88>58,8>5,每次减少55,则8?5=3<58?5=3<5合法。
最后价值为33<4

题解:这题就是快速幂

下面是我的代码:

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
int main()
{int T;scanf("%d",&T);while(T--){long long x,N,M,Y,ans=1;scanf("%lld%lld%lld%lld",&x,&N,&M,&Y);x=x%M;while(N){if(N&1)ans=ans*x%M;x=x*x%M;N=N>>1;}if(ans>Y)printf("YES\n");elseprintf("NO\n");}return 0;
}