【题目描述】

输入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;  }

(adsbygoogle = window.adsbygoogle || []).push({});