【题解】取余运算
【题目描述】
输入b，p，k的值，求bp mod k的值。其中b，p，k×k为长整型数。
【输入描述】
输入b，p，k的值。
【输出描述】
求 b^p mod k的值。
【样例输入】
2 10 9
【样例输出】
2^10 mod 9=7
【题目分析】
从题目给的样例看数据量不大，可以用循环的方式直接求解。
如果题目中的b比较大，那么使用快速幂的求法
用到数论里的(a*b)%7 =(a%7 * b%7)%7
【参考代码1】——不使用任何代码优化
#include<iostream>
using namespace std;
long long a,b,p;
long long ans=1;
int main()
{
cin>>a>>b>>p;
long long tmp=b; //把b先拿出来
while(b!=0)
{
ans=ans*a; //累乘的过程
b--;
}
//cout<<ans<<endl;
ans=ans%p;
cout<<a<<"^"<<tmp<<"mod"<<p<<"="<<ans;
return 0;
}【参考代码2】——使用公式优化
#include<iostream>
using namespace std;
long long a,b,p;
long long ans=1;
int main()
{
cin>>a>>b>>p;
long long tmp=b; //把b先拿出来
while(b!=0)
{
ans=(ans*a)%p; //优化
b--;
}
//cout<<ans<<endl;
ans=ans%p;
cout<<a<<"^"<<tmp<<"mod"<<p<<"="<<ans;
return 0;
}【参考代码3】——快速幂优化
#include<iostream>
using namespace std;
long long a,b,p;
long long ans=1;
int main()
{
cin>>a>>b>>p;//定义底数，次数，取余
long long tmp=b; //把b先拿出来
while(b!=0)
{
if(b%2==1)
ans=(ans*a)%p;
a=(a*a)%p;
b=b/2;
}
//cout<<ans<<endl;
ans=ans%p;
cout<<a<<"^"<<tmp<<"mod"<<p<<"="<<ans;
return 0;
}扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。