P1226 【模板】快速幂||取余运算

给你三个整数 a,b,pa,b,p，求 a^b bmod pabmodp。

输入只有一行三个整数，分别代表 a,b,pa,b,p。

输出一行一个字符串 a^b mod p=s，其中 a,b,pa,b,p 分别为题目给定的值， ss 为运算结果。

输入 #1

2 10 9

输出 #1

2^10 mod 9=7

样例解释

2^{10} = 1024210=1024，1024 bmod 9 = 71024mod9=7。

数据规模与约定

对于 100%100% 的数据，保证 0le a,b < 2^{31}0≤a,b<231，a+b>0a+b>0，2 leq p lt 2^{31}2≤p<231。

模板题，理解不了就把他背下来吧。

#include
using namespace std;
#define ll long long
ll mod(ll a, ll b, ll c) {
	ll sum = 0;
	while (b) {
		if (b & 1)sum = (sum + a) % c;
		a = (a + a) % c;
		b >>=1;
	}
	return sum;
}
ll func(ll a, ll b, ll c) {
	ll ans = 1;
	while (b) {
		if (b & 1)ans = mod(ans, a, c);
		a = mod(a, a, c);
		b >>= 1;
	}
	return ans;
}

int main() {
	ll a, b, c;
	cin >> a >> b >> c;
	cout << a << "^" << b << " mod " << c << "=" << func(a, b, c) << endl;
	return 0;
}