LeetCode 0878. 第 N 个神奇数字
admin
2024-02-07 21:53:44
0次

【LetMeFly】878.第 N 个神奇数字

力扣题目链接：https://leetcode.cn/problems/nth-magical-number/

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

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

 

    示例 1：

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

    示例 2：

    输入：n = 4, a = 2, b = 3
输出：6

     

    提示：

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

     

    方法一：二分查找

    根据鸽巢原理，在1∼x1\sim x1∼x中，有⌊xa⌋+⌊xb⌋−⌊xc⌋\lfloor\frac{x}{a}\rfloor+\lfloor\frac{x}{b}\rfloor-\lfloor\frac{x}{c}\rfloor⌊ax​⌋+⌊bx​⌋−⌊cx​⌋个“神奇数”，其中ccc是aaa和bbb的最小公倍数。

    因此，我们可以直接二分xxx找到第nnn个“神奇数”即可。

    • 时间复杂度O(log⁡(n×min⁡(a,b)))O(\log(n\times\min(a, b)))O(log(n×min(a,b)))
    • 空间复杂度O(1)O(1)O(1)

    AC代码

    C++

    typedef long long ll;
class Solution {
public:int nthMagicalNumber(int n, ll a, ll b) {ll c = lcm(a, b);ll l = min(a, b), r = n * min(a, b);while (l <= r) {ll mid = (l + r) >> 1;if (mid / a + mid / b - mid / c >= n)r = mid - 1;elsel = mid + 1;}return (r + 1) % 1000000007;}
};

    同步发文于CSDN，原创不易，转载请附上原文链接哦~
    Tisfy：https://letmefly.blog.csdn.net/article/details/127978493

    词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

    上一篇：Arduino开发实例-多机CAN-Bus通信（基于MCP2515）

    下一篇：Vue 之 vue3 与 TS 的配合使用整理

    相关内容

    热门资讯

    【MySQL】锁 锁 文章目录锁全局锁表级锁表锁元数据锁（MDL）意向锁AUTO-INC锁...
    【内网安全】 隧道搭建穿透上线... 文章目录内网穿透-Ngrok-入门-上线1、服务端配置：2、客户端连接服务端ÿ...
    GCN的几种模型复现笔记 引言 本篇笔记紧接上文，主要是上一篇看写了快2w字，再去接入代码感觉有点...
    数据分页展示逻辑 import java.util.Arrays;import java.util.List;impo...
    Redis为什么选择单线程？R... 目录专栏导读一、Redis版本迭代二、Redis4.0之前为什么一直采用单线程？三、R...
    【已解决】ERROR: Cou... 正确指令： pip install pyyaml
    关于测试，我发现了哪些新大陆 关于测试 平常也只是听说过一些关于测试的术语，但并没有使用过测试工具。偶然看到编程老师...
    Lock 接口解读 前置知识点Synchronized synchronized 是 Java 中的关键字，...
    Win7 专业版安装中文包、汉... 参考资料：http://www.metsky.com/archives/350.htm...
    3 ROS1通讯编程提高(1) 3 ROS1通讯编程提高3.1 使用VS Code编译ROS13.1.1 VS Code的安装和配置...
    大模型未来趋势 大模型是人工智能领域的重要发展趋势之一，未来有着广阔的应用前景和发展空间。以下是大模型未来的趋势和展...
    python实战应用讲解-【n... 目录 如何在Python中计算残余的平方和 方法1：使用其Base公式 方法2：使用statsmod...
    学习u-boot 需要了解的m... 一、常用函数 1. origin 函数 origin 函数的返回值就是变量来源。使用格式如下...
    常用python爬虫库介绍与简... 通用 urllib -网络库(stdlib)。 requests -网络库。 grab – 网络库&...
    药品批准文号查询|药融云-中国... 药品批文是国家食品药品监督管理局（NMPA）对药品的审评和批准的证明文件...
    【2023-03-22】SRS... 【2023-03-22】SRS推流搭配FFmpeg实现目标检测 说明： 外侧测试使用SRS播放器测...
    有限元三角形单元的等效节点力 文章目录前言一、重新复习一下有限元三角形单元的理论1、三角形单元的形函数（Nÿ...
    初级算法-哈希表 主要记录算法和数据结构学习笔记，新的一年更上一层楼！ 初级算法-哈希表...
    进程间通信【Linux】 1. 进程间通信 1.1 什么是进程间通信 在 Linux 系统中，进程间通信...
    【Docker】P3 Dock... Docker数据卷、宿主机与挂载数据卷的概念及作用挂载宿主机配置数据卷挂载操作示例一个容器挂载多个目...