6064번: 카잉 달력 (구현)

 

 

 

6064번: 카잉 달력

 

간단한 구현문제여서 브루트포스로 풀 수 있을 것 같았는데, 1 ≤ M, N ≤ 40,000 이므로 day를 1~MN까지 확인하는 solve() 처럼 풀면 시간초과가 뜬다. 시간초과를 해결하기 위해 다른 색다른 알고리즘이 필요한 것이 아니라 단지 수식적으로 확인해서 day를 특정하면 된다. 그리고 이 과정에서 solve() 풀이에서 처럼 직접 구현하지 않더라도 모듈러 연산으로 성립조건을 간단히 알아낼 수 있다. 

day1 = mk_1 + x ,day2 = nk_2 + y 꼴로 표현된다. (이때 k1,k2는 0 이상의 자연수이며, 1 ≤ x≤ m ,1 ≤ y ≤ n)

즉 day = x로 두고, 계속해서 m을 더해가며 만약 day가 종말일인 lcd(m,n)를 넘어서면 존재하지 않는다고 생각할 수 있다.

# 브루트포스로는 제한시간땜에 풀 수 없음
def solve(m,n,x,y):
    nx,ny = 0,0
    day = 0
    while nx<m or ny<n:
        if nx<m: nx += 1
        else: nx = 1
        if ny<n: ny += 1
        else: ny = 1
        day += 1
        if nx == x and ny == y:
            return day
    return -1
 
# 따라서 day의 형태를 잡고 변화시키는 범위를 늘리자.
def gcd(a,b):
    while b!=0:
        r = a%b
        a = b
        b = r
    return a
 
def lcd(a,b):
    return a*b/gcd(a,b)
 
def solve1(m,n,x,y):
    day = x
    while True:
        # day = m(k1) + x 꼴인데 1<=x<=m이니까 x에도 모듈러 연산해줌
        if day%m==x%m and day%n==y%n and day <= lcd(m,n):
            return day
        # day가 종말일을 넘어서면 -1 반환
        if day > lcd(m,n):
            return -1
        day += m
 
t = int(input())
for i in range(t):
    m,n,x,y = map(int,input().split())
    print(solve1(m,n,x,y))