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

题目描述
输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。

输入输出格式
输入格式：
三个整数b,p,k.

输出格式：
输出“b^p mod k=s”

s为运算结果

输入输出样例
输入样例#1：
2 10 9
输出样例#1：
2^10 mod 9=7

/*

快速幂
*/

#include <bits/stdc++.h>
using namespace std;
int main()
{
	long long a,b,k;
	long long ans = 1;
	scanf("%ld %ld %ld",&a,&b,&k);
	printf("%lld^%lld mod %lld=",a,b,k);
	while(b>0){
		if(b%2 == 1) ans = (ans*a)%k; //b%2 == 1   <==>  b&2
		b /= 2; //         b /= 2  <==>   b >>= 1
		a = (a*a)%k;
	}
	printf("%lld\n",ans%k);
	return 0;
}