求幂模
Time Limit:
1000MS
Memory Limit:
65536KB
Total Submissions:
118
Accepted:
53
Share
Description:
求c^e÷n的余数(c的e次方除以n的模)。
Input:
输入有一行三个整数c,e,n。
Output:
输出只有一个整数,即所求结果。
Sample Input:
2 10 100
Sample Output:
24
Hint:
0≤c≤1000000000,0≤e≤1000000000,1≤n≤10000, 时间限制≤1秒
Source:
#include
typedef __int64 LL;
int a, k, mod;
int pow_mod(int a, int k, int mod)//非递归
{
int res = 1;
while(k)
{
if(k & 1)
res = ((LL)res * (LL)a) % mod;
k >>= 1;
a = ((LL)a * (LL)a) % mod;
}
return res;
}
int main()
{
while(~scanf("%d%d%d", &a, &k, &mod))//int范围够吗?
printf("%d
", pow_mod(a, k, mod));
return 0;
}