[백준 6064] 카잉 달력

www.acmicpc.net/problem/6064

6064번: 카잉 달력

수학 문제이다. 어렵게 접근하면 한없이 어려워지지만 x를 고정하고 y값을 변화시킨다고 생각하면 쉽다.

-1이 나오는 경우는 <m:n>에 해당하는 마지막 k번째 해를 넘어갈 때인데 k는 m과 n의 최소 공배수이다.

 

++ 최소 공배수 구하기

a와 b의 최소 공배수는 a * b / gcd(a,b)이다.

gcd는 유클리드 호제법을 사용하여 구해주면 된다.

정리하는 김에 코드를 간단히 적어본다.

int gcd(int a, int b)
{
	int r;
    while(b){
    	r = a % b;
        a = b;
        b = r;
    }
    return a;
}

 

 

다시 문제로 돌아와서 k를 구해보자.

k = x로 초기화한다. k는 y값을 대신하며 리턴값이다.

k는 m씩 증가하는데 최대 n을 넘을 수 없으므로 k %= n일 것이다.

 

하지만 k % n == y하면 틀린다. 왜냐면 n이 y와 같을 경우 k가 n의 배수이면 무조건 0이 나오기 때문이다. 

13 11 1 11의 경우 답이 66이지만 66번째에서

22 % 11 = 0 (11이 나와야 함) 

으로 계산하여 66번째에 break를 나오지 못할 것이다.

 

따라서 (k-1) % n + 1 == y를 해줘야 한다.

 

k % n = y  <=>  (k-1) % n + 1 = y인데 그 이유는

www.acmicpc.net/board/view/54865 여기 댓글에 잘 설명되어 있다.

 

(k-1) % n + 1을 해주면 k가 n의 배수이더라도 결과값이 0이되지 않고 n-1이 되어 +1을 했을 때 n이 된다

 

#include <stdio.h>
#include <algorithm>
using namespace std;

int t;
int m, n, x, y;

int LCM(int a, int b)
{
  int lcm = a * b;
  int r;
  while (b)
  {
    r = a % b;
    a = b;
    b = r;
  }

  return lcm / a;
}
int main(void)
{
  scanf("%d", &t);

  while (t--)
  {
    scanf("%d%d%d%d", &m, &n, &x, &y);
    int k = x;

    int lcm = LCM(m, n);
    while (1)
    {
      if (k > lcm)
      {
        k = -1;
        break;
      }
      if ((k - 1) % n + 1 == y)
      {
        break;
      }
      k += m;
    }
    printf("%d\n", k);
  }
  return 0;
}