https://www.luogu.com.cn/problem/P1226

题目描述

给你三个整数 b,p,k，求 b^p mod k。

输入格式

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

输出格式

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

输入输出样例

输入 #1 

1
2 10 9

输出 #1

1
2^10 mod 9=7
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ll a,b,k;
ll binpow(ll a, ll b,ll k) {
  a %= k;
  ll res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % k;
    a = a * a % k;
    b >>= 1;
  }
  return res;
}
int main(){
	freopen("in","r",stdin);
	scanf("%lld%lld%lld",&a,&b,&k);
	printf("%lld^%lld mod %lld=%lld",a,b,k,binpow(a,b,k)%k);
	return 0;
}