878. Nth Magical Number.md

Leetcode

878. Nth Magical Number

: 매직 넘버 ! n, a, b의 정수를 입력받고 a 또는 b로 나눠지는 n번째 수를 구해라. (값이 매우 크면 10^9 + 7로 나눈 나머지를 반환해라)

문제링크

코드

class Solution {
    // 최대공약수
    func GCD(_ min: Int, _ max: Int) -> Int {
        let remain = min % max
        if remain == 0 {
            return max
        }
        else {
            return GCD(max, remain)
        }
    }

    // 최소공배수
    func LCM(_ a: Int, _ b:Int) -> Int {
        return a / GCD(a,b) * b
    }
    
    func nthMagicalNumber(_ n: Int, _ a: Int, _ b: Int) -> Int {
        let MOD = 1_000_000_007
        
        var array : [Int] = []
        let lcm = LCM(a, b)
        
        let M = lcm / a + lcm / b - 1
        let q = n / M
        let r = n % M
        
        var ans = q * lcm % MOD
        if (r == 0) {
            return ans
        }
        
        var ia : Int = a
        var ib : Int = b
        for i in 1..<r {
            if ia < ib {
                ia += a
            } else {
                ib += b
            }
        }
        var di : Int = 0
        if ia > ib {
            di = ib
        } else {
            di = ia
        }
        
        
        return ((ans + di) % MOD)
    }
}

풀이 이유

참고한 내용