[C++] 백준 15829번 Hashing

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

풀이

계산 중 매우 큰 수가 나오면 오버플로우가 발생하여 결과가 달라질 수 있다.

오버플로우 방지를 위해

1. long long 형 사용하기

2. 더하고 곱할 때마다 모듈러 연산 적용하기
   : 덧셈 및 곱셈을 하는 중간 단계에서 얼마든지 나머지를 취해도 최종 결과는 변하지 않음

• 모듈러 연산 법칙

(a mod M + b mod M) mod M = (a + b) mod M
(a mod M × b mod M) mod M = (a × b) mod M

코드

#include <iostream>

using namespace std;

int main()
{
    int L;
    string s;
    cin >> L >> s;
    
    long long ans = 0, r = 1, m = 1234567891;
    
    for(int i=0; i<L; i++) {
        ans = (ans + (s[i] - 'a' + 1) * r) % m;
        r = r * 31 % m;
    }
    
    cout << ans;
    
    return 0;
}