[python] 백준 6064 - 카잉 달력

https://www.acmicpc.net/problem/6064

애증의 카잉달력

 

Q>  M,N보다 작거나 같은 두 숫자 x,y를 가지고 년도를 표현

<M:N> 일 때 종말의 날 <- x,y의 최소공배수

즉, 최소공배수보다 작은 경우 k를 반환하고 아니면 -1

 

🧨 뭔소린가 했지만

결국 60갑자랑 똑같은 원리다ㅜㅜ

(🤩 조원분이 알려주셨다)

60갑자 구하는 법 찾아보고 블로그 뒤져가며 풀었다

 

✨

주석에도 적어놨지만

결국 x와 y는 

k를 m으로 나눈 나머지, k를 n으로 나눈 나머지이다

1. 10 * i + x = 12 * j +y 인 것

    -> x에 10을 계속 더해주고 12로 나누었을 때 나머지가 y와 같으면 (10i+x)가 k가 된다

    -> (10*i + x) % 12 == y

    -> j는 결국 12의 배수이므로 12로 나누어줌

2. 결국 위 식은

    -> (10*i + x)에 y를 빼주고 12로 나누면 0으로 나눠떨어진다는 말이 된다

    -> (10*i + x - y) % 12 ==0 이 되는 것

나무위키 60갑자

def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
    
def lcm(a,b):
    return (a * b) // gcd(a,b)
    
'''
갑자 구하기
k년일 경우 
k = 10 * i + 나머지1(x) == 12 * j + 나머지2(y)
즉, 나머지1(x) + 10*i 를 12로 나누었을 때, 나머지2(y)와 같아야 함 
'''
# 결국 x+(m*i) 를 n으로 나눠준 나머지가 y와 같아야 함
# ==> x에 y를 빼주고 n으로 나누어떨어지면 정답
# 15번째 예시 <5,3>
#  5 % 12 = 5
#  15 % 12 = 3  -> 15번째 해
# --------------------------
# 5 -3 % 12 = 2
# 15 -3 % 12 = 2  -> 15번째 해

def cal(m,n,x,y):
    lcm_ = lcm(m,n)  # 최소 공배수, 멸망의 날(60갑자 참고)
    while x < lcm_:  # 멸망의 날 전까지
        if (x - y) % n == 0:  # x에 y를 빼주고 n으로 나누어떨어지면 정답
            return x
        x += m  # x에 계속 m을 더해줌 (위 주석에서 i)
    return -1

test = int(input())
for _ in range(test):
    m, n, x, y = map(int,input().split())
    print(cal(m,n,x,y))