递归算法

long long quick_pow(int x,int y){
    if (y==1) return x; 
    else if (y%2==0) return (int)pow(quick_pow(x,y>>1),2)%1000;
    else return (int)pow(quick_pow(x,y>>1),2)*x%1000;
}

非递归算法

long long quick_pow(int x,int y){
    int ans=1;
    x%=mod;
    while(y!=0){
        if (y&1) ans=(ans*x)%mod;
        y>>=1;
        x=x*x%mod;
    }
    return ans;
}