题目描述

给你三个整数\(b,p,k\)，求\(b^p \bmod k\)。

输入格式

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

输出格式

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

输入输出样例

输入 #1

2 10 9

输出 #1

2^10 mod 9=7

说明/提示

样例输入输出 1 解释

\(2^{10} = 1024\)，\(1024 \bmod 9 = 7\)。

数据规模与约定

对于\(100\%\)的数据，保证\(b,p < 2^{31}\)，\(1 \leq k \lt 2^{31}\)

推荐学委的快速幂和取余运算

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
ll qpow(ll b,ll p,ll k){
	ll res=1; 
	while(p){
		if(p&1) res=res*b%k;
		b=b*b%k;
		p>>=1;
	}
	return res%k;
}
int main(){
	ll b,p,k;
	scanf("%lld %lld %lld",&b,&p,&k);
	printf("%lld^%lld mod %lld=%lld",b,p,k,qpow(b,p,k));
	return 0;
}