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