首页 > 其他分享 >2023-05-17:一个正整数如果能被 a 或 b 整除,那么它是神奇的。 给定三个整数 n , a , b ,返回第 n 个神奇的数字。 因为答案可能很大,所以返回答案 对 10^9 + 7 取模

2023-05-17:一个正整数如果能被 a 或 b 整除,那么它是神奇的。 给定三个整数 n , a , b ,返回第 n 个神奇的数字。 因为答案可能很大,所以返回答案 对 10^9 + 7 取模

时间:2023-05-17 22:44:24浏览次数:51  
标签:返回 return gcd int long let 答案 ans 神奇

2023-05-17:一个正整数如果能被 a 或 b 整除,那么它是神奇的。

给定三个整数 n , a , b ,返回第 n 个神奇的数字。

因为答案可能很大,所以返回答案 对 10^9 + 7 取模 后的值。

输入:n = 4, a = 2, b = 3。

输出:6。

答案2023-05-17:

过程描述:

1.计算 ab 的最小公倍数 lcm

2.初始化变量 l 为0,变量 r(n * min(a, b)),其中 min(a, b) 表示 ab 中的最小值。在这个范围内通过二分查找获得第 n 个神奇数字。

3.对于每个二分查找猜测值,计算在 ab中出现的神奇数字个数:m/a + m/b。然后计算 ab 的公共倍数 lcmm 范围内出现的神奇数字个数:m/lcm

4.如果出现的神奇数字总数大于或等于 n,则将当前猜测值存储在变量 ans 中,并将右边界向左移动一位(即缩小区间的范围)。

5.如果出现的神奇数字总数小于 n,则将左边界向右移动一位(即扩大区间的范围),并继续迭代。

6.二分查找过程结束后,返回答案 ans % (10^9 + 7)

时间复杂度为 O(logN),空间复杂度为 O(1)。

在这个算法中,使用了二分查找来搜索第 n 个神奇数字。在最坏情况下,二分查找的迭代次数为 O(logN)。因此,时间复杂度为 O(logN)。

另外,在算法中只使用了几个整数变量来存储值和计算结果,所以空间复杂度为 O(1)。

go完整代码如下:

package main

func nthMagicalNumber(n int, a int, b int) int {
	// 求a和b的最小公倍数
	lcm := int64(a / gcd(a, b) * b)
	var ans int64 = 0
	// l = 0
	// r = (long) n * Math.min(a, b)
	l, r := int64(0), int64(n)*int64(min(a, b))
	for l <= r {
		m := (l + r) / 2
		if m/int64(a)+m/int64(b)-m/lcm >= int64(n) {
			ans = m
			r = m - 1
		} else {
			l = m + 1
		}
	}
	return int(ans % 1000000007)
}

func gcd(a int, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	n := 1000000000
	a := 40000
	b := 40000
	result := nthMagicalNumber(n, a, b)
	println(result)
}

在这里插入图片描述

rust完整代码如下:

fn nth_magical_number(n: i32, a: i32, b: i32) -> i32 {
    let n = n as i64;
    let a = a as i64;
    let b = b as i64;
    // 求a和b的最小公倍数
    let lcm = a / gcd(a, b) * b;
    let mut ans = 0;
    // l = 0
    // r = (long) n * Math.min(a, b)
    let mut l = 0;
    let mut r = (n * std::cmp::min(a, b));
    while l <= r {
        let m = (l as i64 + r as i64) / 2;
        if m / a as i64 + m / b as i64 - m / lcm as i64 >= n as i64 {
            ans = m;
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    (ans % 1000000007) as i32
}

fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 {
        a
    } else {
        gcd(b, a % b)
    }
}

fn main() {
    let n = 1000000000;
    let a = 40000;
    let b = 40000;
    let result = nth_magical_number(n, a, b);
    println!("{}", result);
}

在这里插入图片描述

c语言完整代码如下:

#include <stdio.h>

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

int nthMagicalNumber(int n, int a, int b) {
    // 求a和b的最小公倍数
    long long lcm = (long long)a / gcd(a, b) * b;
    long long ans = 0;
    // l = 0
    // r = (long) n * Math.min(a, b)
    for (long long l = 0, r = (long long)n * (a < b ? a : b), m = 0; l <= r;) {
        m = (l + r) / 2;
        if (m / a + m / b - m / lcm >= n) {
            ans = m;
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return (int)(ans % 1000000007);
}

int main() {
    int n = 1000000000;
    int a = 40000;
    int b = 40000;
    int result = nthMagicalNumber(n, a, b);
    printf("%d\n", result);
    return 0;
}

在这里插入图片描述

c++完整代码如下:

#include <iostream>
using namespace std;

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

int nthMagicalNumber(int n, int a, int b) {
    // 求a和b的最小公倍数
    long long lcm = (long long)a / gcd(a, b) * b;
    long long ans = 0;
    // l = 0
    // r = (long) n * Math.min(a, b)
    for (long long l = 0, r = (long long)n * min(a, b), m = 0; l <= r;) {
        m = (l + r) / 2;
        if (m / a + m / b - m / lcm >= n) {
            ans = m;
            r = m - 1;
        }
        else {
            l = m + 1;
        }
    }
    return (int)(ans % 1000000007);
}

int main() {
    int n = 1000000000;
    int a = 40000;
    int b = 40000;
    int result = nthMagicalNumber(n, a, b);
    cout << result << endl;
    return 0;
}

在这里插入图片描述

标签:返回,return,gcd,int,long,let,答案,ans,神奇
From: https://www.cnblogs.com/moonfdd/p/17410563.html

相关文章

  • 接口统一返回工具类
    一、接口统一返回类importcom.alibaba.fastjson.annotation.JSONField;importcom.alibaba.fastjson.serializer.SerializerFeature;importlombok.Data;importjava.io.Serializable;@DatapublicclassResponseMessage<T>implementsSerializable{//返回状态......
  • JVM(四)虚拟机栈(二)栈帧结构:动态链接、方法返回地址与附加信息
    JVM(三)虚拟机栈(二)栈帧结构:动态链接、方法返回地址与附加信息1动态链接技术每一个栈帧,都包含着一个指向运行时常量池中该指针所属方法的引用,即方法区中的方法地址,包含该引用的目的就是为了支持当前方法能够实现动态链接。所以动态链接又称为运行时常量池中的方法引用在java源......
  • vue elementui validate异步校验改成同步校验返回结果
     异步的校验 <script>import{defineComponent,ref}from'vue'exportdefaultdefineComponent({methods:{getFormDataStatus(){letresult=ref(false)this.ruleForm.validate((valid)=>{if(valid){......
  • 查找文本字符串,并返回所在行数据
    #include<iostream>#include<string>#include<Windows.h>#include<fstream>#include<sstream>#include<signal.h>#include<io.h>#include<vector>#include<process.h>#include<cstdio>#include<as......
  • Django authenticate() 函数查找不到与提交的用户名和密码匹配的用户,则会返回 None。
    在你的userAPP下面添加一个utils.py文件classUsernameMobileBackend(ModelBackend):defauthenticate(self,request,username=None,password=None,**kwargs):"""重写人做方法"""#使用账号查询运河#如果用户名查询到用......
  • Delphi-Delphi通过管道执行外部命令行程序(cmd)并获取返回结果
     相关资料:https://www.shuzhiduo.com/A/gGdXxNGmd4/     Delphi通过管道执行外部命令行程序(cmd)并获取返回结果实例代码:unitUnit1;interfaceusesWinapi.Windows,Winapi.Messages,System.SysUtils,System.Variants,System.Classes,Vcl.Graphics,Vcl.......
  • ETL测试工具和面试常见的问题及答案
     概述        商业信息和数据对于任何一个企业而言都是至关重要的。现在很多公司都投入了大量的人力、资金和时间对这些信息、数据进行分析和整理。数据的分析和整理已经获得了巨大的潜在市场,因此为了使得这个过程更为简单,越来越多的软件供应商引入了ETL测试工具。目前,有......
  • 关于有朋友遇到的使用 ChatGPT 获得 SAP 相关问题答案不够准确的困扰和我的解答
    笔者的SAP开发技术交流群里,有朋友提问:求教一下,哪位大侠知道查看主配方(事务代码C203)的界面里面,那个工序的资源字段是怎么取出来的(从哪个数据表来的)?多谢这个朋友反馈,在他提问之前,询问了ChatGPT同样的问题,但感觉ChatGPT回答的质量不高:以下是我的解答:ChatGPT不是......
  • C#异步方法async/await的三种返回类型
    有群友问C#异步方法async返回值Task和void的区别?看似简单,但不容易把它们用好。在C#中的异步编程已经成为现代编程的标配,异步方法(async/await)是实现异步编程的一种常用方式。在异步方法中,可以使用Task或void作为返回类型,还可以使用ValueTask返回类型。本文将介绍异步方法中3个......
  • httprunner 4.x学习 - 4.提取返回结果与校验(extract, validate)
    执行命令:hrprun.\test_extract.yml--gen-html-report日志:6:03PMINFvalidatestatus_codeassertMethod=eqcheckExpr=status_codecheckValue=200checkValueType=int64expectValue=200expectValueType=int64result=true6:03PMINFrunstependexportVars={"ag......