快速幂和快速乘取模

(a + b) % p = (a%p + b%p) %p
(a - b) % p = ((a%p - b%p) + p) %p
(a * b) % p = (a%p)*(b%p) %p

代码

#include 
using namespace std;
typedef long long LL;
LL pow_mod(LL a,LL b,LL c) // 快速幂取模 
{
	LL ans = 1;
	a = a % c;
	while(b)
	{
		if(b&1)
			ans = (ans * a) % c;
		a = (a * a) % c;
		b >>= 1;
	}
	return ans;
}
LL q_mul(LL a,LL b,LL c) // 快速乘取模 
{
	LL ans = 0;
	a = a % c;
	while(b)
	{
		if(b&1)
			ans = (ans + a) % c;
		a = (a + a) % c;
		b >>= 1;
	}
	return ans;
}
int main()
{
	LL a,b,c,chiose;
	cin >> chiose;
	cin >> a >> b >> c;
	switch(chiose)
	{
		case 1:cout << pow_mod(a,b,c) << endl;break;
		case 2:cout << q_mul(a,b,c) << endl;break;
	}
}