快速幂

_shining · 2024-04-13 17:32:53 · 算法·理论

快速幂

题目背景：

求 n^m mod k (m \le 2^{31})

完整代码：

#include <iostream>//cin cout 
using namespace std;//命名空间
long long n, m, k;
long long ksm(long long n, long long m, long long k)
{
    long long ans = 1;
    while(m){
        if(m & 1) ans = ((ans % k) * (n % k)) % k;//同余定理
        n = ((n % k) * (n % k)) % k;
        m >>= 1;
    }
    return ans;
}
int main()//主函数
{
    cin >> n >> m >> k;
    cout << ksm(n, m, k);
    return 0;//华丽结束
}