繰り返し二乗法（C++）
(num_theory/pow.cpp)

• View this file on GitHub
• Last update: 2023-09-17 18:47:10+09:00

概要

繰り返し二乗法を行います。

計算量

• 指数を $N$ として $O(logN)$

補足

Pythonなら下記コードで自動的に繰り返し二乗法を行ってくれる。 $a^b$を $mod$ で割った余りを $O(log(b))$ で出してくれる。

pow(a,b,mod)

Verified with

• verify-check/AOJ-NTL-1-B.test.cpp

Code

#include <iostream>
using namespace std;

const long long MOD = 1000000007;  // 10^9 + 7

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

#line 1 "num_theory/pow.cpp"
#include <iostream>
using namespace std;

const long long MOD = 1000000007;  // 10^9 + 7

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

Back to top page