백준 6064번 카잉 달력 - 스위프트(Swift) 풀이 + 그림 설명

1. <a, b>에서 a를 x로 고정한다. → <x, b>
2. a를 x로 고정하면 고려해야할 경우의 수는 N/GCD가지이다.
3. N/gcd가지 중에 b = y인 경우가 있는지 확인한다.

---

1. <a, b>에서 a를 x로 고정한다. → <x, b>

 1번째 해부터 마지막 해까지 모두 고려하면, M, N이 최대 40,000이므로 O(N^2)으로는 시간초과가 나게 된다. 둘 중에 하나를 고정해서 O(N)에 해결이 가능하도록 하자.

 

 

2. a를 x로 고정하면 고려해야할 경우의 수는 N/GCD가지이다.

 M = 3, N = 2인 경우를 생각해보자. <a,b>라고 하면 a자리는 1, 2, 3이 반복되고 b자리에는 1, 2가 반복된다. 따라서 M과 N의 최소공배수번째 해에 <M, N>이 될 것이다.  총 LCM개의 해 중에서 a = x인 경우는 총 LCM / M가지가 될 것이다. 이때 LCM / M = (N * M / GCD) / M = N / GCD 이므로 총 N/GCD가지 경우의 수를 고려해주면 된다.

 

 

 

3. N/gcd가지 중에 b = y인 경우가 있는지 확인한다.

 각각의 경우에서 b의 값은 어떻게 구할까? b자리에는 1, 2, 1, 2...가 반복되므로 나머지 연산으로 구할 수 있다. k번째 해의 b는 k % N이 된다.(k % N == 0일 때는 N으로 예외 처리 필요.)

 i번째 경우를 고려하고 있을 때는 k = (i - 1) * M + x번째 해이므로 이 두 사실을 조합해서 b를 구할 수 있다.

 

---

import Foundation

func gcd(_ A: Int, _ B: Int) -> Int {
    if B == 0 { return A }
    
    return gcd(B, A % B)
}

func solution() -> String {
    var result = ""
    var T = Int(readLine()!)!
    
    while T > 0 {
        let input = readLine()!.split(separator: " ").map{ Int(String($0))! }
        let M = input[0]
        let N = input[1]
        let X = input[2]
        let Y = input[3]
        
        let gcd = N > M ? gcd(N, M) : gcd(M, N)
        var findSolution = false
        
        for i in 1...(N/gcd) {              // x를 기준으로 x가 X가 되는 모든 해를 고려, 총 N/gcd개 고려
            let k = (i - 1) * M + X         // k번째 해
            let y = k % N == 0 ? N : k % N  // k번째 해일 때 y값
            
            if y == Y {
                result.write("\(k)\n")
                findSolution = true
                break
            }
        }
        
        if !findSolution { result.write("-1\n") }
        
        T -= 1
    }
    
    return result
}

print(solution())