快速幂（NO. 2035）

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #define mod 1000
 5 
 6 int rapidly_power(int base, int power);
 7 
 8 int main(void) {
 9     int a, b;
10 
11     while (~scanf("%d %d", &a, &b) && a && b) {
12         int result = rapidly_power(a, b);
13 
14         printf("%d
", result);
15     }
16     
17     return 0;
18 }
19 
20 int rapidly_power(int base, int power) {
21     int result = 1;
22 
23     while (power > 0) {
24         //如果指数是奇数，那么取出一个底数，然后把指数减一，比如2^{3 =}2*2²，此时2在result中。
25         if (power & 1) result = result * base % mod;
26         //因为(power-1)/2 和power/2结果十一样的
27         //之后，指数减半，底数加倍，如上例子，2²,此时为4¹，之后乘到result里，就是8咯
28         //如此循环，直至指数变为1，那么现在的底数就是结果
29         power >>= 1;
30         base = base * base % mod;
31     }
32 
33     return result;
34 }