백준 15829 : Hashing - C++

 

나머지 연산(mod)은 분배가 가능하다는 점을 다시 되새기고 갑시다.

 

$$(A+B)modM=(AmodM+BmodM)modM$$

$$(A\ast B)modM=(AmodM\ast BmodM)modM$$

$$(A-B)modM=(AmodM-BmodM+M)modM$$

 

A - B의 나머지를 연산하는 과정에서 자칫 음수가 나올 수 있으므로 M을 더해주었습니다.

 

#include <iostream>
#include <string>

using namespace std;

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

	int l, temp;
	long long res = 0;
	long long r = 1;

	cin >> l;

	char c;
	for (int i = 0; i < l; ++i) {
		cin >> c;

		temp = c - 'a' + 1;
		res += temp * r;
		r *= 31;

		if (i > 6 && r >= 1234567891) r = r % 1234567891;
		if (res >= 1234567891) res = res % 1234567891;
	}

	cout << res;

	return 0;
}