음하하하

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

위 문제를 O(1)로 풀 방법이 있나 찾아보다가

[중국인의 나머지 정리]라는 것을 찾았다.

이론에 대한 설명은 아래에 자세히 나와있다.

https://namu.wiki/w/%EC%A4%91%EA%B5%AD%EC%9D%B8%EC%9D%98%20%EB%82%98%EB%A8%B8%EC%A7%80%20%EC%A0%95%EB%A6%AC#fn-10

다음은 BOJ 1476 날짜계산을 푸는 과정이다.

(28 * 19 * e) % 15 == (532 * e) % 15 == (7 * e) % 15 == 1

(15 * 19 * s) % 28 == (285 * s) % 28 == (5 * s) % 28 == 1

(15 * 28 * m) % 19 == (420 * m) % 19 == (2 * m) % 19 == 1

e == 13, s == 17, m == 10

[포인트 1]

(532 * e) % 15 == (7 * e) % 15

[포인트 2]

(7 * e) % 15 == 1

e의 값은 위 식을 만족하는 수 아무거나 고르면 되긴 하지만, 가장 작은 값을 찾는게 빠름

ANSWER = (E * 28 * 19 * 13 + S * 15 * 19 * 17 + M * 15 * 28 * 10) %  (15 * 28 * 19)

             = (E * 6916 + S * 4845 + M * 4200) % 7980