题目描述

给定 $a, b, p$，求 $a^b$ $mod$ $p$。

基本思路

根据快速幂的思想，可顺势得到快速乘的思想，进而完成代码实现。

C++ 代码

#include <iostream>

#define Ull unsigned long long

using namespace std;

Ull quickMul( Ull a, Ull b, Ull p )
{
    Ull res=0, base=b;
    while ( a )
    {
        if ( a & 1 ) res = (res+base)%p;
        base = (base+base)%p;
        a >>= 1;
    }
    return res;

}

int main()
{
    Ull a, b, p, s;
    cin >> a >> b >> p;
    s = quickMul(a, b, p);
    cout << s << endl;
    return 0;

}