ACMICPC 6064 카잉 달력

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 

카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M 과 N 보다 작거나 같은 두 개의 자연수 x, y를 가지고 

각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 

두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 X < M 이면 x' = x + 1이고, 

그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 

<M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11 번째 해는 <1:11>로 표현된다. 

<3:1>은 13 번째 해를 나타내고, <10:12>는 마지막인 60 번째 해를 나타낸다. 

네 개의 정수 M, N, x 와 y가 주어질 때, 

<M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는 지를 구하는 프로그램을 작성하라. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 

입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 

각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 

여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 

여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 

즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

문제를 푸는 법은 읽고나서 바로 생각났는데, 뭔가 시행착오가 많아서 3번이나 틀린 후에야 정답을 제출할 수 있었다.

일단 첫번째로 알 수 있는 사실은 카잉달력의 마지막 해 <M:N> = M*N년 이라는 것이다.

또한 i,j를 임의의 정수라고 하였을때 k 번째 해인 <X:Y>를 풀어쓰면

k = M*i+X = N*j+Y 라는 수식이 성립함을 알 수 있다.

이제 우리는 이를 만족하는 i, j 값이 있는지만 알아내면 된다. (코드에서 find_year 함수의 내용)

만약 m*n이 되도록 이를 만족하는 i,j 값이 없다면 <x:y>가 유효하지 않은 표현이므로 -1을 출력해주면 된다.

오답의 이유

find_year 함수에서 처음에는 if ((m*i+x-y) % n == 0) 대신 if ((m*i+x) % n == y) 를 사용하였었다.

얼핏 보기에는 동일한 답이 나올것같지만 n = 1 일 때 두번째 수식은 좌항이 항상 0이 나와 false 가 된다.

바보같은 실수지만 신경 안 쓰면 왜 틀렸는지 못 찾고 넘어갈 수도 있었을 것 같아 추가로 적어본다.

#include <stdio.h> int find_gcd(int a,int b) { int mod = a % b; while(mod > 0) { a = b; b = mod; mod = a % b; } return b; } int find_year(m, n, x, y, lcm) { int i = 0; while(m*i+x <= m*n) { if ((m*i+x-y) % n == 0) return m*i+x; i++; } return -1; } int main() { int t, m, n, x, y, gcd, lcm; scanf("%d", &t); while(t--) { scanf("%d%d%d%d", &m, &n, &x, &y); gcd = find_gcd(m, n); lcm = m*n/gcd; printf("%d\n", find_year(m, n, x, y, lcm)); } }