【基础】快速幂 - Problem Detail - 追梦算法网

ID: 749

Type: Default

1000ms

16MiB

Difficulty: 10

Uploaded By:

Tags>

noip

说明

求x^p mod m 的值。
提示：若 p 为偶数，x^p=(x²)^p/2；若 p 为奇数，x^p=x*(x²)^(p-1)/2，该题可以采用分治法求解。

输入格式

三个不超过 10000 的正整数 x，p，m。

输出格式

x^p mod m 的值。

样例

2 10 100

提示

noip2017普及组初赛