Programming/Algorithm
[백준] 6064번 카잉 달력 (by Python)
oranz.23
2021. 3. 7. 20:33
문제
https://www.acmicpc.net/problem/6064
6064번: 카잉 달력
입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다.
www.acmicpc.net
풀이
from math import gcd
import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
m, n, x, y = map(int, input().split())
if n > m:
m, n = n, m
x, y = y, x
k = x
y = 0 if n == y else y
end = (m * n) // gcd(m, n)
while k <= end:
if k % n == y:
break
k += m
print(-1 if k > end else k)
나머지를 이용한 문제라는 것을 눈치채는 것이 중요한 문제. 나타낼 수 있는 해의 가짓수는 M과 N의 최소공배수로 정해지고, K는 M으로 나누었을 때 나머지가 X, N으로 나누었을 때 나머지가 Y인 수이다. 그렇기 때문에 M과 N의 최소공배수 범위 내에서 X에서 M씩 증가시키며 N으로 나누었을 때 나머지가 N인 수를 찾았다. M이 클수록 빨리 찾는 데에 유리했기 때문에, 해당사항을 보장해주는 코드 또한 포함하였다.