BOJ(카잉달력)(6064)

작성일 | In

건너 뛰며 해보기

  • 문제의 정답을 구하기 위해서 모든 경우의 수를 살펴봐야 하는 건 맞지만,
  • 어떤 특정한 경우는 정답이 안나오기 때문에, 굳이 경우의 수로 시도해볼 필요가 없는 경우를 말한다.
  • M,N,x,y가 주어졌으 때, <x:y>이 몇 번째 해인지 구하는 문제
  • 그런데, 이 문제도 날짜계산 문제처럼 다 만들어야 할까?
  • 1 <= M,N <= 40,000

  • 전체 경우의 수는 16억 가지라서 너무 많다.

  • No Image

  • 각각의 주기가 존재한다, 5와 7이라는.
  • 모든 수에서 1만큼만 빼보자.
  • 그러면 x,y를 쉽게 구할 수 있다.
  • 0,1,2,3,4가 반복되기 때문이다.

  • 23 % 5, 23%7 을 하면 3,2가 나오게 된다.

  • x=3, y=2라면, 정답은 <3,2>가 나와야 한다.
  • 모든 정답이 될 수 있는 후보는 5로 나눈 나머지가 3이 나와야 한다.

  • 첫 번째 3부터 계속 n씩 증가하면서, 정답을 비교해보면 된다. y가 같은지.

  • x를 이용해 모든 고려하지 않고, ix(M+x)(i>=0)

  • M으로 나눈 나머지가 x인 모든 연도에 대해서만 조사를 하면 된다.

  • 이 방법이 가능한 이유는, x를 고정했으면, 가능한 y는 n개 밖에 없기 때문이다.
  • 조사해봐야 하는 연도는 최대 n개만 나오게 된다.
t = int(input())
for _ in range(t):
    m,n,x,y = map(int,input().split())
    x -= 1
    y -= 1
    k = x
    while k < n*m:
        if k%n == y:
            print(k+1)
            break
        k += m
    else:
        print(-1)

참고자료 codeplus

0%