[BOJ 11505 구간 곱 구하기] 나머지연산(%)의 분배 법칙
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";
}
}
}