6-1 Quick Power (4 分)
The function Power calculates the exponential function Nk. But since the exponential function grows rapidly, you are supposed to return (Nk)%10007 instead.
Format of function:
int Power(int N, int k);
Both N and k are integers, which are no more than 2147483647.
Sample program of judge:
#include <stdio.h>
int Power(int, int);
const int MOD = 10007;
int main()
{
int N, k;
scanf("%d%d", &N, &k);
printf("%d\n", Power(N, k));
return 0;
}
/* Your function will be put here */
Sample Input 1:
2 3
Sample Output 1:
8
Sample Input 2:
128 2
Sample Output 2:
6377
作者
沈鑫
单位
浙江大学
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
Answer:
int Power(int N, int k)
{
N %= MOD;
if (k == 0)
return 1;
if (k > 0) {
if (k % 2 == 1)
{
return N * Power(N, k - 1) % MOD;
k /= 2;
}
else
{
k /= 2;
return Power(N, k)*Power(N, k) % MOD;
}
}
}