累乗の剰余 (modpow)
目的
累乗を素数で割った際の剰余を求める。
コード
long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; }
コードテスト
#include <iostream> using namespace std; // a^n mod を計算する long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } int main() { // 3^45 mod. 1000000007 を計算してみる cout << modpow(3, 45, 1000000007) << endl; }
