Binary-Power(繰り返し二乗法) (math/binpow.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-05 17:45:04+09:00

Verified with

• test/aoj_NTL_1_B.cpp
• test/atc_arc117_c.cpp
• test/yuki_1035.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

long long binpow(long long a, long long ex, long long p = (1LL << 61) - 1) {
	long long res = 1;
	while(ex > 0) {
		if(ex & 1) (res *= a) %= p;
		ex >>= 1;
		(a *= a) %= p;
	}
	return res;
}

#line 2 "math/binpow.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

long long binpow(long long a, long long ex, long long p = (1LL << 61) - 1) {
	long long res = 1;
	while(ex > 0) {
		if(ex & 1) (res *= a) %= p;
		ex >>= 1;
		(a *= a) %= p;
	}
	return res;
}

Back to top page