최근에 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>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.
문제로만 보면 잘 이해가 가지 않는다.
고로, M=3, N=4로 예시를 들어보았다.
1번째 해: <1,1>
2번째 해: <2,2>
3번째 해: <3,3>
4번째 해: <1,4>
5번째 해: <2,1>
6번째 해: <3,2>
7번째 해: <1,3>
8번째 해: <2,4>
9번째 해: <3,1>
10번째 해: <1,2>
11번째 해: <2,3>
12번째 해: <3,4>
이렇게 x=M, y=N일 시인 마지막 해는 12번째 해이다.
(M과 N의 최소공배수)
여기서 <2,1>이 몇번째 해인지 찾는다고 하자
x=2이니 2번째 해일 가능성이 있다.
다음으로 x=2인 구간은 5번째, 8번째, 11번째이다.
이처럼 M만큼 건너뛰면서 x가 동일한 구간을 확인할 수 있다.
여기서 순서(i)를 N으로 나눈 값이 y를 N으로 나눈 값과 같다면 해당 해가 구하는 답이다.
> 사실 처음에는 i%N==y면 되지 않을까, 했는데 i%N이 0이고 y가 N인 경우가 있기에 i%N==y%N으로 처리했다.
따라서 코드로 작성하면
for (int i=x; i<=M*N; i+=N)
if(i%N==y)
return i;
가 된다.
찾지 못하면 -1을 출력하도록 처리해준다.
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
int func(int M, int N, int x, int y)
{
for (int i = x; i <= M*N; i += M)
{
if (i % N == y%N)
return i;
}
return -1;
}
int main() {
int tc;
scanf("%d", &tc);
while (tc--)
{
int M, N, x, y;
scanf("%d %d %d %d", &M, &N, &x, &y);
printf("%d\n", func(M, N, x, y));
}
return 0;
}
cin, cout 시간초과 처리해주기 귀찮아서 그냥 scanf, prinf로 작성했다.