华华教月月做数学——快速幂
2023-12-14 20:04:11
找到了心仪的小姐姐月月后,华华很高兴的和她聊着天。然而月月的作业很多,不能继续陪华华聊天了。华华为了尽快和月月继续聊天,就提出帮她做一部分作业。
月月的其中一项作业是:给定正整数A、B、P,求 A^B mod P 的值。华华觉得这实在是毫无意义,所以决定写一个程序来做。但是华华并不会写程序,所以这个任务就交给你了。
因为月月的作业很多,所以有T组询问.
Input
第一行一个正整数 T (1 ≤ T ≤ 1e3),表示测试数据组数。
接下来 T 行,每行三个正整数 A, B, P (1 ≤ A, B, P ≤ 1e18),含义如上
输入:
2
2 5 10
57284938291657 827493857294857 384729583748273
输出:
2
18924650048745
解析:
单单用快速幂是求不出答案的.
代码一
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int N=2e6+10;
int qmu(int a,int k,int p) //快速乘
{
a %=p;
int ans=0;
while (k)
{
if (k&1) ans=(ans+a)%p;
k >>=1;
a=(a+a)%p;
}
return ans;
}
int qmi(int a,int k,int p) //快速幂
{
a %=p;
int ans=1;
while (k)
{
if (k&1) ans=qmu(ans,a,p)%p;
k >>=1;
a=qmu(a,a,p)%p;
}
return ans;
}
int a,b,p,t;
signed main()
{
ios;
cin>>t;
while (t--)
{
cin>>a>>b>>p;
cout<<qmi(a,b,p)<<endl;
}
return 0;
}
代码二
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int N=2e6+10;
__int128 qmi(int a,int k,int p) //(__int128 + 快速幂)
{
a %=p;
__int128 ans=1;
while (k)
{
if (k&1) ans=ans*a%p;
k >>=1;
a=(__int128)a*a%p;
}
return ans%p;
}
int a,b,p,t;
signed main()
{
ios;
cin>>t;
while (t--)
{
cin>>a>>b>>p;
int ans=qmi(a,b,p);
cout<<ans<<endl;
}
return 0;
}
文章来源:https://blog.csdn.net/m0_74403543/article/details/135001950
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!