给出3个正整数A B C，求A^B Mod C。

例如，3 5 8，3^5 Mod 8 = 3。

 收起

输入

3个正整数A B C，中间用空格分隔。(1 <= A,B,C <= 10^9)

输出

输出计算结果

输入样例

3 5 8

输出样例

3

---

---

 

#include<iostream>
using namespace std;

int main(){
	long long ans=1;
	int a,b,c;
	cin>>a>>b>>c;
	
	for(int i=1;i<=b;i++){
		ans=(ans*a)%c;
	}
	cout<<ans<<endl;
	return 0;
}

时间复杂度O(n)，超时了。

---

#include<iostream>
using namespace std;

int pow_mod(int a,int n,int m){
	if(n==0) return 1;
	int x=pow_mod(a,n/2,m);
	long long ans=(long long)x*x%m;
	if(n%2==1) ans=ans*a%m;
	return (int)ans;
}

int main(){
	int a,b,c;
	cin>>a>>b>>c;
	cout<<pow_mod(a,b,c)<<endl;
	return 0;
}

---

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	long long  a,b,c,d,sum=1;
	cin>>a>>b>>c;
	while(b)
	{
		if(b%2==1)
			sum=(sum*a)%c;
		b>>=1;
		a=(a*a)%c;
	}
	cout<<sum<<endl;
	return 0;
	
}

OK,

指数减半。