[c++][BOJ] Hasing

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

15829번: Hashing

문자열이 들어오면 문자에 숫자를 부여해서 자리마다 차례대로 31의 거듭제곱을 곱하는 문제입니다.

 

하지만 큰 문제가 있는데, 바로 자리수가 너무 커진다는 것입니다. 예를 들어 50자리 문자라면 마지막 문자에는 31의 49제곱이 곱해지는 문제가 있습니다.

 

그래서 중간중간에 나머지로 나누어주는 코드를 넣어서 범위가 벗어나지 않게 합니다.

#include <iostream>
#include <string>
using namespace std;

int main(){
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    
    long long t = 1;
    long long sum = 0;
    long long mul;
    
    for(int i=0; i<n; i++)
    {
        char c = s[i];    
        
        c -= 96;
        mul = (c * t) % 1234567891;
        sum += mul;
        sum = sum % 1234567891;
        t *= 31;
        t = t % 1234567891;
    }
    
    sum = sum % 1234567891;
    cout << sum;
}