https://www.acmicpc.net/problem/1476
위 문제를 O(1)로 풀 방법이 있나 찾아보다가
[중국인의 나머지 정리]라는 것을 찾았다.
이론에 대한 설명은 아래에 자세히 나와있다.
다음은 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