PS를 하다 보면 아래와 같은 조건이 자주 등장한다.

첫째 줄부터 K줄에 걸쳐 구한 구간의 곱을 1,000,000,007로 나눈 나머지를 출력한다.

문제 풀이 시 불필요한 overflow 문제가 발생하지 않도록 하기 위한 조건이다.

내가 오늘 푼 BOJ 11050도 이 내용을 가지고 있었다.

https://www.acmicpc.net/problem/11505

이 조건을 충족시키기 위해서는??

이런 식으로 overflow가 발생할 가능성이 있는 파트에 모듈러 연산을 추가해야 한다.

example = (example * val) % 1000000007;
example = (example + val) % 1000000007;

중요한 사실: 나누기(/) 연산에 대해 모듈러 연산의 분배법칙이 성립하지 않는다!!!

(a + b) % mod = ( (a % mod) + (b % mod) ) % mod // 성립!!
(a - b) % mod = ( (a % mod) - (b % mod) ) % mod // 성립!!
(a * b) % mod = ( (a % mod) * (b % mod) ) % mod // 성립!!


(a / b) % mod = ( (a % mod) / (b % mod) ) % mod // 성립 X

나눗셈에서 mod 분배법칙은 특정한 조건에서만 성립한다.

즉, 일반적으로 성립하지 않는다.

(이걸 모르고 풀었다가 호되게 당했다…. 괜히 알고리즘에 문제있는 줄 알고 엉뚱한 곳 뜯어 고칠 뻔)

나머지 연산의 분배 법칙

첫 풀이에서는 아래와 같은 방식이었다.

void update_segtree(int idx, ll val) {
	ll prevval = segtree[idx];
	segtree[idx] = val;
	idx /= 2;
	while(idx > 0) {
		if(prevval == -1) segtree[idx] = (segtree[idx] * val) % 1000000007;
		else if(prevval == 0) segtree[idx] = segtree[idx*2] * segtree[idx*2 + 1] % 1000000007;
		/////////////////////// 아래 코드의 나누기 연산이 문제!!! ///////////////////////////
		else segtree[idx] = segtree[idx] / prevval * val % 1000000007;
		idx /= 2; 
	}
}

나누기 연산을 사용하지 않는 방식으로 수정하였다!!

(사실 저 문제되는 line은 삭제해도 상관 없었다. 그 앞의 else if에 해당하는 부분에서 처리 가능하다. 그래서 그냥 삭제했다.)

void update_segtree(int idx, ll val) {
	ll prevval = segtree[idx];
	segtree[idx] = val;
	idx /= 2;
	while(idx > 0) {
		if(prevval == -1) segtree[idx] = (segtree[idx] * val) % 1000000007;
		else segtree[idx] = (segtree[idx*2] * segtree[idx*2 + 1]) % 1000000007;
		idx /= 2; 
	}
}

틀렸던 풀이 전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

int n, m, k, K = 1;;
vector<ll> segtree;

void init_segtree() {
	for(int KK = K/2; KK > 0; KK/=2) {
		for(int i=KK; i<KK*2; i++) {
			// 비어있는 노드라면,
			if(segtree[i*2] == -1 && segtree[i*2 + 1] == -1) segtree[i] = -1;
			else if(segtree[i*2 + 1] == -1) segtree[i] = segtree[i*2];
			else if(segtree[i*2] == -1) segtree[i] = segtree[i*2+1]; // 아마 존재 X 경우일 듯
			else segtree[i] = segtree[i*2] * segtree[i*2 + 1] % 1000000007;;
		}
	}
}

void update_segtree(int idx, ll val) {
	ll prevval = segtree[idx];
	segtree[idx] = val;
	idx /= 2;
	while(idx > 0) {
		if(prevval == -1) segtree[idx] = (segtree[idx] * val) % 1000000007;
		else if(prevval == 0) segtree[idx] = segtree[idx*2] * segtree[idx*2 + 1] % 1000000007;
		else segtree[idx] = segtree[idx] / prevval * val % 1000000007;
		idx /= 2; 
	}
}

ll search(int l, int r) {
	ll mulsum = 1;
	while(l <= r) {
		if(l%2 == 1) {
			mulsum = (mulsum * segtree[l]) % 1000000007;
			l++;
		}
		if(r%2 == 0) {
			mulsum = (mulsum * segtree[r]) % 1000000007;
			r--;
		}
		l /= 2; r /= 2;
	}
	return mulsum;
}

void print_segtree() {
	for(int i=1; i<K+n; i++) {
		cout << segtree[i] << " | ";
	} cout << endl << endl;
}

int main() {
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int a, b, c;
	cin >> n >> m >> k;

	while(K <= n) K *= 2;
	segtree.resize(K*2 + 1);

	// -1로 segtree 초기화
	for(int i=0; i<K*2+1; i++) segtree[i] = -1;

	for(int i=0; i<n; i++) {
		cin >> segtree[K + i];
	}
	init_segtree();
	// print_segtree(); // for test;

	for(int i=0; i<m + k; i++) {
		cin >> a >> b >> c;
		if(a == 1) { // b번째 수를 c로 바꾸기
			update_segtree(K+b-1, c);
			// print_segtree(); // for test
		}
		else if(a == 2) { // b ~ c 구간 곱 출력
			cout << search(K + b - 1, K + c - 1) % 1000000007 << "\n";
		}
	}
}

정답 풀이 - 나누기 모듈러 수정

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using ll = long long;

int n, m, k, K = 1;;
vector<ll> segtree;

void init_segtree() {
	for(int KK = K/2; KK > 0; KK/=2) {
		for(int i=KK; i<KK*2; i++) {
			// 비어있는 노드라면,
			if(segtree[i*2] == -1 && segtree[i*2 + 1] == -1) segtree[i] = -1;
			else if(segtree[i*2 + 1] == -1) segtree[i] = segtree[i*2];
			else if(segtree[i*2] == -1) segtree[i] = segtree[i*2+1]; // 아마 존재 X 경우일 듯
			else segtree[i] = segtree[i*2] * segtree[i*2 + 1] % 1000000007;;
		}
	}
}

void update_segtree(int idx, ll val) {
	ll prevval = segtree[idx];
	segtree[idx] = val;
	idx /= 2;
	while(idx > 0) {
		if(prevval == -1) segtree[idx] = (segtree[idx] * val) % 1000000007;
		else segtree[idx] = (segtree[idx*2] * segtree[idx*2 + 1]) % 1000000007;
		// else segtree[idx] = segtree[idx] / prevval * val % 1000000007;
		// 나누기는 % 분배법칙 성립하지 않는다?!
		idx /= 2; 
	}
}

ll search(int l, int r) {
	ll mulsum = 1;
	while(l <= r) {
		if(l%2 == 1) {
			mulsum = (mulsum * segtree[l]) % 1000000007;
			l++;
		}
		if(r%2 == 0) {
			mulsum = (mulsum * segtree[r]) % 1000000007;
			r--;
		}
		l /= 2; r /= 2;
	}
	return mulsum;
}

void print_segtree() {
	for(int i=1; i<K+n; i++) {
		cout << segtree[i] << " | ";
	} cout << endl << endl;
}

int main() {
    ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int a, b, c;
	cin >> n >> m >> k;

	while(K <= n) K *= 2;
	segtree.resize(K*2 + 1);

	// -1로 segtree 초기화
	for(int i=0; i<K*2+1; i++) segtree[i] = -1;

	for(int i=0; i<n; i++) {
		cin >> segtree[K + i];
	}
	init_segtree();
	// print_segtree(); // for test;

	for(int i=0; i<m + k; i++) {
		cin >> a >> b >> c;
		if(a == 1) { // b번째 수를 c로 바꾸기
			update_segtree(K+b-1, c);
			// print_segtree(); // for test
		}
		else if(a == 2) { // b ~ c 구간 곱 출력
			cout << search(K + b - 1, K + c - 1) % 1000000007 << "\n";
		}
	}
}