BOJ 15829 - Hashing / C++

문제 링크 : https://www.acmicpc.net/problem/15829

15829번: Hashing

 

 

풀이

해당 수식을 계산하는 과정에서 31^49와 같은 매우 큰 수를 계산하게 되므로 C++의 pow를 사용하면 오버플로우가 발생한다.

따라서 직접 pow 함수를 구현하며 계산 과정에서 modulo 연산을 수행해준다.

나머지는 단순 수식 구현이므로 생략한다.

 

 

코드

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

#define ull unsigned long long

ull pow(int a, int b) {
    ull ret = 1;
    for(int i=0; i<b; i++){
        ret *= a;
        ret %= 1234567891;
    }

    return ret;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n;
    string str;
    cin >> n >> str;

    ull ans = 0;

    for(int i=0; i<n; i++){
        ans += (int(str[i]-'a' + 1) * pow(31, i));
        ans %= 1234567891;
    }

    cout << ans;
}