[C++] 백준 15829번 Hashing

컴공을 전공하면 정수론을 배운다

정수론에서 가장 중요한 것은 개인적으로 모듈러 연산인 것 같다

(이거에 대해서 한 학기동안 배운 것 같다)

모듈러 연산은 나머지 연산이며

이거는 코딩할때 간단히 나머지 연산자만 사용하면 된다

이 문제를 풀때 조건을 제대로 안읽어서 m, r 값을 뭐라고 해야할지

한참 고민했었다.

문제만 제대로 읽었으면 쉽게 풀었을 것 같다

 

나중에 한번에 나머지 연산을 해주는 것 보다는

바로바로 숫자에 대해서 나머지 연산을 해주는 것이 좋다

안그러면 long long을 넘어가는 정수가 저장되어 에러가 날 수도 있다

 

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

#define r 31
#define m 1234567891

int main() {

	int n;
	cin >> n;

	string s;
	cin >> s;

	long long hash = 0;

	for (int i = 0; i < s.length(); i++) {
		int alphabet = s[i] - 'a' + 1;
		long long temp = alphabet;
		for (int k = 0; k < i; k++) {
			temp *= r;
			temp %= m;
		}
		hash += temp;
	}
	cout << hash % m << "\n";

	return 0;
}