快速幂

//第一种效率低下的算法, time cost = 16.91s

typedef long long ll;
const int mod = 1000;
ll normalPower(ll base, ll power){
  ll result = 1;
  for(int i=1; i<=power; i++){
    result = result * base;
    result = result % mod;
  }
  return result % mod;
}

//升级版，time cost = 0.003s
ll fastPower(ll base, ll power){
    ll result = 1;
    while(power > 0){
        if(power%2 == 0){ //指数减半，基数加倍
            power = power/2;
            base = base * base % mod;
        }else{  //指数减一，求模运算一次
            power = power - 1;
            result = result * base % mod;
            //再次执行一次降指数操作
            power = power / 2;
            base = base * base % mod;
        }
    }
    return result;
} 

//代码优化版 time cost <= 0.003s
ll fasterPower(ll base, ll power){
    ll result = 1;
    while(power > 0){
        if(power%2 == 1){ //为奇数，执行一次操作
            result = result * base % mod;
        }
        //power/2会化奇为偶
        power = power/2;
        base = (base * base) % mod;
    }
    return result;
}

//极限优化，使用位运算 time cost = 0.001s
ll fastestPower(ll base, ll power){
    ll result = 1;
    while(power > 0){
        if(power & 1){ //为奇数，执行一次操作
            result = result * base % mod;
        }
        //power/2会化奇为偶
        power >>= 1;
        base = (base * base) % mod;
    }
    return result;
}