龟速乘【模板】

龟速乘用于较大数乘法，因为较大数的乘法会容易爆范围，故采用“安全加法换乘法，时间换空间”的龟速乘。当然也可以不用龟速乘，在容易爆范围的地方强制转换__int128位即可

代码如下，规律是，一个乘数做底，一个做指数，乘法变加法 

# include
# include
# include
 
using namespace std;
typedef long long int ll;
# define mod 10007
ll quick(ll a,ll b)
{
    ll sum=0,pow=b;
 
    while(pow)
    {
        if(pow&1)
            sum=(sum+a)%mod;
        a=(a+a)%mod;
 
        pow>>=1;
    }
    return sum%mod;
}
int main ()
{
 
 
    int a,b;
 
    cin>>a>>b;
 
    cout<<quick(a,b);
    
    return 0;
 
}