878. 第 N 个神奇数字

878. 第 N 个神奇数字

一个正整数如果能被 a 或 b 整除，那么它是神奇的。

给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。

• 输入：n = 1, a = 2, b = 3
• 输出：2

<herf="https://leetcode.cn/problems/nth-magical-number/">题目链接

容斥+二分答案

class Solution {
public:
    using ll = long long int;
    ll gcd(ll a,ll b){
        if(b==0)    return a;
        return gcd(b,a%b);
    }
    int nthMagicalNumber(int n, int a, int b) {
        ll left=min(a,b),right=min(a,b)*(ll)n;
        while(left<=right){
            ll c=a*b/gcd(a,b);
            ll mid=left+(right-left)/2;
            if((mid/a+mid/b-mid/c)>=n)
                right=mid-1;
            else
                left=mid+1;
        }
        return left%(1000000007);
    }
};