math

접근처음에는 ((A % M) + (B % M)) % M = (A+B) % M 을 사용하는 문제라고 생각했다. A + B == C일 때, ((A % M) + ((C - A) % M)) % M = C % M를 활용하면 될 것 같았는데, 수가 최대 1,000,000,000까지이므로 인덱스를 어디로 잡는지가 문제였다. 제한 시간이 초과되었고, 알고리즘을 확인해보니 유클리드 호제법이 있었다. 이전에도 몇 번 접했지만 자주 쓰지 않을 거라고 판단해서 그 때 그 때마다 찾아서 확인했었다. 자주 접하게 되어서 아예 에라토스테네스의 체처럼 기억을 해둘 필요를 느꼈다. 유클리드 호제법두 양의 정수 a, b(a > b)에 대하여 a = bq + r (0 ≤ r gcd(a, b) = gcd(b, r) 반복문 방식def euc..