모듈러(Modular) 연산

---

(A + B) mod C = (A mod C + B mod C) mod C
(A - B) mod C = (A mod C - B mod C) mod C
(A * B) mod C = (A mod C * B mod C) mod C

빠른 거듭 제곱(Fast Exponentiation) 연산

---

A^B % C (B % 2 == 0, B가 짝수일 경우)
= ((A^B/2 mod C) * (A^B/2 mod C)) mod C

EX_1. A = 3, B = 4, C = 5;
3^4 % 5
= ((3^2 % 5) * (3^2 % 5)) % 5
= (4 * 4) % 5
= 1

A^B % C (B % 2 == 1, B가 홀수일 경우)
= ((A^B/2 mod C) * (A^B/2 mod C) * (A^1 mod C)) mod C

EX_2. A = 3, B = 5, C = 5;
3^5 % 5
= ((3^2 % 5) * (3^2 % 5) * (3^1 % 5)) % 5
= (4 4 3) % 5
= 3

모듈러, 빠른 거듭 제곱을 활용한 풀이 코드

---

백준 1629

// 0 <= A, B, C <= 2,147,483,647

#include<iostream>

using namespace std;

typedef long long ll;

ll fast_exponentiation_modular(ll base, ll exponent, ll divisor) {
	long long m = base % divisor;
	
	if(exponent <= 2) return exponent == 1 ? m : (m * m) % divisor;
	
	ll res = fast_exponentiation_modular(base, exponent / 2, divisor);
	
	// exponent가 짝수일 경우 A의 최종 승수 값
	// exponent가 홀수일 경우 최종적으로 A^1 mod C를 해줘야 함으로 한 번 더 mod를 계산해줘야 한다. 
	res = (res * res) % divisor;
	
	if(exponent % 2 == 1) res = (res * m) % divisor;
	
	return res;
}

// EX) B = 5
// 0. A^5 mod C
// 1. A^2 mod C -> A^5/2 mod C
// 2. (A^1 mod C * A^1 mod C) mod C -> A^2 mod C
// 3. (A^2 mod C * A^2 mod C) mod C -> A^4 mod C
// 4. (A^4 mod C * A^1 mod C) mod C -> A^5 mod C

int main() {
	ll a, b, c;
	cin >> a >> b >> c;
	
	ll res = 0;
	
	res = fast_exponentiation_modular(a, b, c);
	
	cout << res;
	
	return 0;
}

백준4375

// n (n % 2 != 0 && n % 5 != 0
// n (1 <= n <= 10000)
// n (모든 자릿수가 1로만 구성)

#include<iostream>
#include<string>

using namespace std;

typedef long long ll;

int base = 10;
string res = "";

ll modular_multi(ll pre_pow_m, int divisor) {
	return (pre_pow_m * (base % divisor)) % divisor;
}

int main() {
	int divisor = 0;
	
	while(cin >> divisor) {
		ll sum_m = 1 % divisor;
		ll pow_m = 1 % divisor;
		ll digit = 1;
		
		while(sum_m != 0) {
			pow_m = modular_multi(pow_m, divisor);
			sum_m = (sum_m + pow_m) % divisor;
			digit++;
		}
		
		res += to_string(digit) + "\n";
	}
	
	cout << res;
	
	return 0;
} 

정리

---

모듈러 연산의 장점: 실제 값에 대한 계산 없이 나머지를 구할 수 있다. 값의 범위로 인한 오버플로우 문제를 예방할 수 있다.
빠른 거듭 제곱 연산의 장점: 시간 복잡도를 O(N) -> O(log N)으로 단축시킬 수 있다.