CPP教程-快速幂

C++教程

快速幂

代码实现：
第一种：

#include 
using namespace std;

int f(int m, int n) { //m^n
    if (n == 1)
        return m;
    int temp = f(m, n / 2);
    return (n % 2 == 0 ? 1 : m) * temp * temp;
}

int main() {
    long long a, b;
    cin >> a >> b;
    cout << f(a, b);

}

第二种：

ll ksm(int a,int b,int p)
{
    ll res=1;
    while(b)
    {
        if(b&1)res=(res*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return res;
}

快速乘

ll mul()
{
    ll res=0;
    while(b)
    {
        if(b&1)res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return res;
}