LG#P1226. 【模板】快速幂

【模板】快速幂

P1226 【模板】快速幂

题目描述

\hspace{15pt}给你三个整数 a,b,pa,b,p,求 ab mod pa^b \bmod p。

输入格式

\hspace{15pt}在一行上输入三个整数 $a,b,p \left(0 \leqq a,b < 2^{31};\ a+b > 0;\ 2 \leqq p < 2^{31}\right)$ 分别代表底数、指数和模数。

输出格式

\hspace{15pt}在一行上输出一个字符串,格式为 a^b mod p=s,其中 a,b,pa,b,p 分别为题目给定的值,ss 为运算结果。

测试样例

2 10 9

2^10 mod 9=7

样例 1 解释

\hspace{15pt}210=10242^{10} = 1024,1024 mod 9=71024 \bmod 9 = 7。