卡速米 get！

A4paper · 2018-04-10 17:10:33 · 个人记录

传送门

int FastPow(int a, int x)
{
    int ans = 1;
    while(x)
    {
        if(x & 1) ans = ans * a % p;
        a = a * a % p;
        x >>= 1;
    }
    return ans;
}

补充：卡速乘

利用二进制将乘法转化成加法

20＊14 = 20＊(1110) = 20＊(2^3)＊1 + 20＊(2^2)＊1+20＊(2^1)＊1+20＊(2^0)＊0 = 160+80+40=280.

int FastMul(int a, int x) //快速乘法
{
    int ans = 0;
    while(x)
    {
        if(x & 1)   ans = (ans+a) % p;
        a = (a+a) % p;
        x >>= 1;
    }
    return ans;
}