龟速乘【模板】

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

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

# include<iostream>
# include<iomanip>
# include<math.h>

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;

}