2118: 取余运算

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：7 Solved：1

Description

输入b，p，k的值，求bp mod k的值。其中b，p，k。

Input

一行，b, p, k，以空格隔开。（1000 <= p <= 2^64 - 1）

Output

一行，输出形式为b^p mod k=xxx。 (等号前后无空格)

其中xxx为计算出的结果。

Sample Input Copy 

2 10 9

Sample Output Copy 

2^10 mod 9=7

HINT

A*B%K = (A%K )*(B% K )%K

P=2 * (P/2) + P%2，如19=2 * (19/2) + 19%2=2*9+1

Source/Category