TLE的乘幂

提交数: 914, 通过率: 28.88%, 平均分: 47.35

题目描述:

TLE讨厌长长的题面。因此他出了一句话题面:给出a,b,c,求a^b(a的b次方)在mod c意义下的值。

输入格式:

第一行3个整数a,b,c。

输出格式:

输出共一行,一个整数,为题意所求的答案。

样例输入:

6 2 10

样例输出:

6

提示:

对于40%的数据,a<=2000,b<=3000,c<=4000;

对于70%的数据,b<=300000;

对于100%的数据,1<=a<=1e9,1<=b<=2e9,1<=c<=2e9

例子:计算 6100  % 10

6^100=(6^50)*(6^50)%10

6^50=(6^25)*(6^25)%10

6^25=(6^12)*(6^12)%10*6%10

6^12=(6^6)*(6^6)%10

6^6=(6^3)*(6^3)%10

6^3=(6^1)*(6^1)%10*6%10

注意:每次乘了以后对c取余,不然会超出范围。

时间限制: 1000ms
空间限制: 128MB

来源: by cyb