[백준] 6064번: 카잉 달력

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

initial

Wow i mean i did a whole shit show by trying to solve this. I tried guessing the answer by taking the smallest m or n value, and if m is smaller, doing (m+1)*x would give the correct answer for x. Then, whil value x isnt changed in the clock, if we can increment (guess % n) up to value y, then that is the answer.

But my pattern doesnt work for some cases and most importantly, it is unnecessarily complex to implement. So look for other ways in this case always.

https://devum.tistory.com/83

I googled and found this is finding a common point between 2 clocks that have diff starting points and cycles. I still dont get how you derive this pattern (tbc). But we add m to x and x is gonna be the current time. When (x-y)%n==0, that means our current time - starting time of y is divisible by n (i.e. LCM of both cycle m and n that satisfies starting point of x and y).

But what if (x-y)%n==0 condition is met prematurely and value x is less than what the question gave us? Im not sure (tbc) Oh wait I thought value x appears only once in this syncrhoisation cycle but actually, x appears multiple times like when x==3, it is when it is day 3, 13, 23, 33, etc.

We increment x until the GCM of m and n, which is mn. But rmb x can be that GCD so condition should be (x<=mn)

solution

import sys
input = sys.stdin.readline

def calc(m, n, x, y):
    while x <= m * n:
        if (x - y) % n == 0:
            return x
        else:
            x += m
    return -1

t = int(input())
for _ in range(t):
    m, n, x, y = map(int, input().split())
    result = calc(m, n, x, y)
    print(result)

complexity

Let's analyze the time and space complexity of the provided code:

Time Complexity:

The time complexity is primarily determined by the while loop inside the calc function, where it iterates until x exceeds the maximum possible time, which is m * n.

• The loop iterates at most m * n / m = n times.
• The operations inside the loop are constant time.

Therefore, the overall time complexity is O(n) where n is the value of n.

Space Complexity:

The space complexity is minimal in this case, as the algorithm uses only a constant amount of space for variables (m, n, x, y, result, and loop variables).

Therefore, the space complexity is O(1) or constant.

In summary, the time complexity is O(n) and the space complexity is O(1) for the provided code.