华华教月月做数学
时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 32768K,其他语言65536K
64bit IO Format: %lld
题目描述
找到了心仪的小姐姐月月后,华华很高兴的和她聊着天。然而月月的作业很多,不能继续陪华华聊天了。华华为了尽快和月月继续聊天,就提出帮她做一部分作业。
月月的其中一项作业是:给定正整数A、B、P,求ABmodPABmodP的值。华华觉得这实在是毫无意义,所以决定写一个程序来做。但是华华并不会写程序,所以这个任务就交给你了。
因为月月的作业很多,所以有T组询问。
输入描述:
第一行一个正整数T表示测试数据组数。 接下来T行,每行三个正整数A、B、P,含义如上文。
输出描述:
输出T行,每行一个非负整数表示答案。
示例1
输入
2 2 5 10 57284938291657 827493857294857 384729583748273
输出
2 18924650048745
备注:
1≤T≤1031≤T≤103,1≤A,B,P≤1018
题解:这是一道快速幂取模的题,如果直接快速幂取模,还是会爆long long还需要进一步分解。但是python就能过,c++在linux环境下大数据__int128也能过的。
如下大佬:
但是一般都是在Windows下面编译的,就不行了,需要进一步分解。
如果不知道快速幂,这里给出博主认为不错的博客传送门:https://blog.csdn.net/dbc_121/article/details/77646508
python 版快速幂取模:
def pow_mod(a,b,mod):
ans=1
a=a%mod
while(b):
if b&1:ans=ans*a%mod
a=a*a%mod
b>>=1
return ans
t=int(input())
for i in range(t):
a,b,p=map(int,input().split())
print(pow_mod(a,b,p))
c++ 版快速幂取模:
#include<bits/stdc++.h>
using namespace std;
long long mul(long long a,long long b,long long mod)
{
long long ans=0;
while(b)
{
if(b&1) ans=(ans+a)%mod;
a=(a+a)%mod;
b>>=1;
}
return ans;
}
long long pow_mod(long long a,long long b,long long mod)
{
long long ans=1;
while(b)
{
if(b&1) ans=mul(ans,a,mod);
a=mul(a,a,mod);
b>>=1;
}
return ans;
}
int main()
{
long long t,a,b,p;
cin>>t;
while(t--)
{
cin>>a>>b>>p;
cout<<pow_mod(a,b,p)<<endl;
}
return 0;
}