특정한 연도 표시법으로 표시할 수 있는 가장 큰 연도를 출력하는 문제입니다. 문제의 규칙을 읽어보면 연도 표시법이 <x:y>인데, x와 y는 각각 M과 N보다 작거나 같습니다. <1:1>은 1년을 나타내고, 1년이 늘어날 때마다 x와 y 모두 1씩 증가하거나, 상한에 도달한 상태인 경우 1로 돌아갑니다. 즉, M=5, N=7일 때 <4:7>의 다음은 <5:1>이 됩니다. 이 문제는 결국 특정 연도를 M과 N으로 나눈 나머지가 주어졌을 때 이를 만족하는 최소값을 구하는 문제입니다. <x:y>는 결국 M으로 나눈 나머지가 x이고 N으로 나눈 나머지가 y인 연도를 구하라는 것이죠.
우선 답이 나오지 않는 경우를 먼저 알아보겠습니다. M과 N의 관계에 따라 답이 나오지 않는 경우가 생길 수 있습니다. M과 N의 최대공약수를 G라고 쓰고, M=aG, N=bG라고 쓰겠습니다. 이 때 x와 y를 G로 나눈 나머지가 다르다면 답이 존재하지 않습니다. 그 이유는 x가 1인 경우 존재할 수 있는 y의 값이 1부터 N 전체가 아니기 때문입니다. x를 1로 고정시키려면 한 번에 M씩 더하면서 검사해야 하는데, M=aG이기 때문에 y에 M을 더해가면 존재할 수 있는 집합은 \(G\mathbb{Z}+1/N\mathbb{Z}\)가 됩니다. 그런데 N은 bG이므로 이 집합은 \(\{1, (G+1)\bmod{N}, (2G+1)\bmod{N}, ... , ((b-1)G+1)\bmod{N}\}\)로 크기가 b가 됩니다. 이 집합은 x가 1일 때였고, 일반적인 경우를 보면 \(\{x, (G+x)\bmod{N}, (2G+x)\bmod{N}, ... , ((b-1)G+x)\bmod{N}\}\)이고, 여기에 속하지 않는 y에 대해서는 존재할 수 없는 경우가 됩니다.
이제 답을 찾는 과정을 알아보겠습니다. 먼저 x와 y 중 하나를 1로 만들고, 1을 만드는 데에 뺀 만큼 다른 변수도 빼줍니다. x를 1로 만들고 y를 x-1만큼 뺐다고 가정하겠습니다. 우선 이 x-1을 어딘가에 저장합니다. 그리고 y에서 M을 빼고 N으로 나눈 양의 나머지를 구하는 작업을 나머지가 1이 될 때까지 합니다. 이 횟수에 M을 곱한 값을 앞의 저장한 값에 더해줍니다. 그러면 이 값은 1년으로부터 지금까지의 연도가 됩니다. 즉, n년이라면 n-1이 나오는 것이죠. 저장한 값에 1을 더하면 n이 되므로 이것이 답이 됩니다.
소스 코드
| 언어 | 코드 | 시간 |
|---|---|---|
| Python 3 | 코드(Github) / 코드(백준) | 2020-04-01 20:30:53 |