首页 > 试题广场 >

最小公倍数与最大公约数

[编程题]最小公倍数与最大公约数

热度指数：4270 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

度度熊请你找出两个数 $\mathit a,b$ ，满足 $1 \leq a,b \leq n$ 且 $\mathit lcm(a,b)-gcd(a,b)$ 尽量大。输出最大的 $\mathit lcm(a,b)-gcd(a,b)$ .
其中 $\mathit lcm(a,b)$ 表示 $\mathit a$ 和 $\mathit b$ 的最小公倍数， $\mathit gcd(a,b)$ 表示 $\mathit a$ 和 $\mathit b$ 的最大公约数。

输入描述:

一行一个数字。

输出描述:

一行一个数字表示最大的。

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

牛客754407944号


	#include <iostream>
using namespace std;
int main(){
    long long n;
    cin>>n;
    cout<<n*(n-1)-1;
}

编辑于 2021-08-27 21:26:53 回复(3)

木木醒醒

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String next = sc.next();
        int a = Integer.parseInt(next);
        int b = a-1;
        String a1 = a+"";
        String b1 = b+"";
        BigInteger a2 = new BigInteger(a1);
        BigInteger b2 = new BigInteger(b1);
        BigInteger one = new BigInteger("1");
        BigInteger result = (a2.multiply(b2).subtract(one));
        System.out.println(result);
    }

发表于 2021-06-07 17:44:56 回复(0)

Java

牛客217455925号

import java.util.*;

public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Long a = sc.nextLong();
System.out.println(a*(a-1)-1);
}
}

发表于 2023-03-07 13:50:09 回复(0)

hahhahaha

结果为：n * (n - 1) - 1。要使lcm(a, b) - gcd(a, b)尽量大，应该让lcm(a, b)尽量大，gcd(a, b)尽量小。

当a=n、b=n-1 时满足该条件：最小公倍数为两者乘积，最大公约数为1

发表于 2023-07-25 01:42:00 回复(0)

_起一个响亮的名字吧

/* 最小公倍数与最大公约数，求n下任意两个数的（最小公倍数-最大公约数）的最大值 */
#include <bits/stdc++.h>
using namespace std;

int main()
{
    unsigned long long int n;
    cin >> n;
    unsigned long long int max=0;
    while(n>1){
        if((n * (n-1) -1) > max){
            max=n * (n-1) -1;
        }
        n--;
    }
    cout << max << endl;
    return 0;
}

发表于 2022-08-17 14:05:15 回复(3)

王同学想拿offer

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

long gcd (long a, long b) {

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

}

void slove() {

ll n;

cin >> n;

cout << (n * (n - 1) / gcd(n,n - 1) - gcd (n, n - 1));

}

signed main() {

ios::sync_with_stdio(0);

cin.tie(0);

int t = 1;

while(t--){

slove();

}

return 0;

}

发表于 2023-04-09 10:10:36 回复(0)

爱上Coding

直接用数学方法算通式：n*(n-1)-1

public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别   long n = in.nextLong(); System.out.print(n*(n-1)-1);
}

发表于 2023-09-27 22:55:03 回复(0)

hencejacki

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        in.close();
        System.out.println((n * (n - 1)) / gcd(n, n - 1) - gcd(n, n - 1));
    }

    public static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}

发表于 2023-04-02 22:59:00 回复(0)

Java

面基人

import java.util.Scanner;
import java.math.BigInteger;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
//真的容易超时，还得是大整数相乘啊
    public static void process(String n) {
        if (n.charAt(0) == '1') {
            System.out.println(1);
            return ;
        }
        BigInteger n1 = new BigInteger(n);
        BigInteger n2 = new BigInteger(n);
        BigInteger n3= n2.subtract(new BigInteger("1"));
        BigInteger res=n1.multiply(n3).subtract(new BigInteger("1"));
        System.out.println(res);
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String n = in.next();
            process(n);
        }
    }
}

发表于 2023-03-29 21:45:22 回复(0)

刘汉东

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
long n = in.nextInt();
long result = n*(n-1) - 1;
System.out.println(result);
}
}
}

发表于 2023-03-27 16:46:30 回复(0)

xcrj

// 哈哈哈 超时
public class Main {
    public static void main(String[] args) {
        long n=0;
        Scanner in=new Scanner(System.in);
        if(in.hasNextLong()){
            n=in.nextLong();
        }
        long mr=Long.MIN_VALUE;
        for(long a=1;a<=n;a++){
            for(long b=1;b<=n;b++){
                // 求最小公倍数
                long x=gbshu(a, b);
                // 求最小公约数
                long y=(a*b)/x;
                // 相减
                mr=Math.max(mr, x-y);
            }
        }
        System.out.println(mr);
    }

    public static long gbshu(long a , long b) {
        //
        if(a%2!=0&&b%2!=0&&a==b){
            return a;
        }
        //
        long ra=0;
        long ca=0;
        while(true){
            if(a%2!=0){
                ra=a;
                break;
            }else{
                a=a/2;
                ra=a;
                ca++;
            }
        }
        //
        long rb=0;
        long cb=0;
        while(true){
            if(b%2!=0){
                rb=b;
                break;
            }else{
                b=b/2;
                rb=b;
                cb++;
            }
        }
        //
        long c=Math.max(ca, cb);
        long d=1;
        for(long i=0;i<c;i++){
            d*=2;
        }
        return ra*rb*d;
    }
}

发表于 2023-03-14 22:41:17 回复(0)