//
// Created by 罗炳国 on 2023/11/2.
//

#ifndef PFJ_CODE027_NTHMAGICALNUMBER_H
#define PFJ_CODE027_NTHMAGICALNUMBER_H
#include "commonHeader.h"

/**
 * 一个正整数如果能被 a 或 b 整除，那么它是神奇的。
 * 给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 1000000007 取模 后的值。
 * https://leetcode.cn/problems/nth-magical-number/
 * */

class code027_nthMagicalNumber {
public:
    int nthMagicalNumber(int n, int a, int b) {
        long lcmv = lcm(a, b);
        int ans;
        long l = 0, r = (long)n * min(a, b);
        while (l <= r) {
            long mid = l + ((r - l) >> 1);
            if ((mid / a) + (mid / b) - (mid / lcmv) >= n) {
                ans = mid % 1000000007;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return ans % 1000000007;
    }

    void test() {

    }

private:
    long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    long lcm(long a, long b) {
        return (long)a / gcd(a, b) * b;
    }
};

#endif//PFJ_CODE027_NTHMAGICALNUMBER_H