LeetCode878. Nth Magical Number

一、题目

A positive integer is magical if it is divisible by either a or b.

Given the three integers n, a, and b, return the nth magical number. Since the answer may be very large, return it modulo 109 + 7.

Example 1:

Input: n = 1, a = 2, b = 3
Output: 2
Example 2:

Input: n = 4, a = 2, b = 3
Output: 6

Constraints:

1 <= n <= 109
2 <= a, b <= 4 * 104

二、题解

最大公约数，同余定理，二分答案。

class Solution {
public:int nthMagicalNumber(int n, int a, int b) {int mod = 1e9 + 7;long long lcm = a / gcd(a,b) * b;long long res = 0;long long l = 0,r = (long long)n * min(a,b);while(l <= r){long long mid = (l + r) / 2;if(mid / a + mid / b - mid / lcm >= n){res = mid;r = mid - 1;}else{l = mid + 1;}}return res % mod;}
};