【题目描述】

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