Summary

结果这篇也咕了几天呢 qwq,
就是讲一下快 (ka) 速(su)幂 (mi) 啦.

Text

快速幂(与龟速乘)

Code:

long long ksc(long long a, long long b, long long p)
{
    long long re = 0;
    while (b)
    {
        if (b & 1)
        {
            re += a;
            re %= p;
        }
        a += a;
        a %= p;
        b >>= 1;
    }
    return re;
}
 
long long ksm(long long a, long long b, long long p)
{
    long long re = 1;
    while (b)
    {
        if (b & 1)
            re = ksc(a, re, p);
        a = ksc(a, a, p);
        b >>= 1;
    }
    return re;
}

显然是不会有解释说明的嘛 qwq.