本文介绍: 最大公约数,同余定理,二分答案。

文章目录

一、题目

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;
    }
};

原文地址:https://blog.csdn.net/weixin_46841376/article/details/135521448

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。

如若转载,请注明出处:http://www.7code.cn/show_55228.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注