快速幂

// a^k%p
int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k&1) res = res * a % p;
        a = a*a %p;
        k>>=1;
    }
    return res; 
}

龟速加

// a*b%p
// a,b,p都是比较大的数
typedef long long LL;
LL qadd(LL a, LL b, LL p)
{
    LL res = 0;
    while(b)
    {
        if(b&1) res = (res+a)%p;
        a = (a+a)%p;
        b>>=1;
    }
    return res;
}