首页 > 试题广场 >

小乐乐与欧几里得

[编程题]小乐乐与欧几里得
  • 热度指数：79708 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

小乐乐最近在课上学习了如何求两个正整数的最大公约数与最小公倍数，但是他竟然不会求两个正整数的最大公约数与最小公倍数之和，请你帮助他解决这个问题。


输入描述:
每组输入包含两个正整数n和m。(1 ≤ n ≤ 109，1 ≤ m ≤ 109)


输出描述:
对于每组输入，输出一个正整数，为n和m的最大公约数与最小公倍数之和。
示例1

输入

10 20

输出

30
示例2

输入

15 20

输出

65
算法知识视频讲解
添加回答
梦想还是要有的丶头像 梦想还是要有的丶
z最大公约数通过辗转相除法求的
最小公倍数=两数之积/最大公约数 
#include<iostream>
using namespace std;
//最大公约数
int gcd(int a,int b)
{
    if(a%b==0)
        return b;
    else
        return gcd(b,a%b);
}

int main()
{
    long m,n,maxD,minM,result;
    while(cin>>m>>n)
    {
        maxD=gcd(m,n);
        minM=m*n/maxD;
        result=maxD+minM;
        cout<<result<<endl;
    }
    return 0;
}


发表于 2020-07-27 22:44:19 回复(0)
李浩1993头像 李浩1993
记录一下。 
import java.awt.font.FontRenderContext;
import java.lang.reflect.Array;
import java.util.*;
import java.io.IOException;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        long m = sc.nextInt();
        long temp, p=n, q=m;
        if (n < m){
            temp = n;
            n = m;
            m = temp;
        }
        long r;
        do {
            r = n % m;
            n = m;
            m = r;
        }while (r != 0);

        long min = (p * q) / n;
        System.out.println(min + n);
    }
}


发表于 2020-06-29 14:33:11 回复(1)
C/C++
牛客690803919号头像 牛客690803919号 
#include <iostream>
using namespace std;
long M(long a,long b)//最大公约数
{
    long c,t;
    c=a%b;
    while(c)
    {
        t=b;
        b=c;
        c=t%c;
    }
    return b;
}
int main()
{
    long long m,n,k;
    cin>>n>>m;
    if(n>=m)
        k=M(n,m);
    else
        k=M(m,n);
    cout<<k+n*m/k<<endl;//其中n*m/k为最小公倍数
    return 0;
}

发表于 2020-03-28 09:13:04 回复(0)
viod头像 viod

求最大公约数常用的有两种方法，一是九章算术中的更相减损术：大数减小数直到相等，相等的数即最大公约数，该算法时间复杂度约为O(N)；二是欧几里得的辗转相除法：大数除以小数取余数(相当于模运算)，直到余数为零时(也即模运算为零时)的除数(也即模数)就是最大公约数，该算法时间复杂度约为O(logN)。

求最小公倍数的方法：原始数据的乘积除以最大公约数。

本题数据偏大，选择时间效率更高的辗转相除法更好，第一次提交没通过，发现一组测试用例的输出竟然是负数，一猜肯定是溢出了，然后把数据类型声明改为long long型： 

#include<stdio.h>
int main(){
    long long a,b,comax,comin,k;
    scanf("%lld %lld",&a,&b);
    k=a*b;
    while(a&&b){
        if(a>b) a %=b;
        else b %= a;
    }
    comax=a>b?a:b;
    comin=k/comax;
    printf("%lld\n",comax+comin);
}

发表于 2021-06-06 17:38:45 回复(2)
Python3
左空一头像 左空一 
n, m = map(int,input().split())
ma = max(n, m)
mi = min(n, m)
r = ma % mi
while r != 0:
    ma = mi
    mi = r
    r = ma % mi
print(int(mi + n*m//mi))

发表于 2021-09-01 09:46:21 回复(1)
aliuselly头像 aliuselly 
#include <stdio.h>
int main(void)
{
    long n, m;
    scanf("%ld %ld", &n, &m);
    
    // 百度一下欧几里得算法，得出最大公约数，就是 a 了
    long a = (n > m ? n : m), b = (n > m ? m : n), temp = 0;
    while (b != 0)
    {
        a %= b;
        temp = a;
        a = b;
        b = temp;
    }
    
    // 有了最大公约数后，我们可以通过百度词条中的最小公倍数可以知道公式法
    // 即：两个数的乘积等于这两个数的最大公约数和最小公倍数的积。
    // 上面已经通过欧几里得算法求出最大公约数 a 了
    // n * m / a 就是求出最小公倍数，然后 + a 就是答案了
    printf("%ld\n", ((n * m) / a) + a);
    return 0;
}

发表于 2021-01-29 10:05:03 回复(0)
C
面向对象的修勾很慢热头像 面向对象的修勾很慢热 
#include<stdio.h>
int main()
{
    long long a=0;
    long long b=0;
    scanf("%d %d",&a,&b);
    long long sum=1;
    long long n=a*b;//求出积
    //辗转相除法，求最大公约数
    while(sum=a%b)
    {
        a=b;
        b=sum;
        //最后最大公约数为b
    }
    //最小公倍数=n/b
    long long m=n/b;
    printf("%lld\n",m+b);//最小公倍数+最大公约数
    return 0;
}

发表于 2022-08-09 22:41:21 回复(0)
C
天下第二也挺好头像 天下第二也挺好

求最大公约数常用的有两种方法，一是九章算术中的更相减损术：大数减小数直到相等，相等的数即最大公约数，该算法时间复杂度约为O(N)；二是欧几里得的辗转相除法：大数除以小数取余数(相当于模运算)，直到余数为零时(也即模运算为零时)的除数(也即模数)就是最大公约数，该算法时间复杂度约为O(logN)。

求最小公倍数的方法：原始数据的乘积除以最大公约数。

本题数据偏大，选择时间效率更高的辗转相除法更好，第一次提交没通过，发现一组测试用例的输出竟然是负数，一猜肯定是溢出了，然后把数据类型声明改为long long型：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<stdio.h>
intmain(){
    longlonga,b,comax,comin,k;
    scanf("%lld %lld",&a,&b);
    k=a*b;
    while(a&&b){
        if(a>b) a %=b;
        elseb %= a;
    }
    comax=a>b?a:b;
    comin=k/comax;
    printf("%lld\n",comax+comin);
}

发表于 2022-07-29 21:51:20 回复(0)
C
Excellent.白头像 Excellent.白 
#include <stdio.h>
int main()
{
    long int m=0;
    long int n=0;
    long int k=0;
    long int a=0;
    long int b=0;
    long int c=0;
    scanf("%ld %ld",&n,&m);
    b=n;
    c=m;
    while((n%m)!=0) //辗转相除法，直至余数为0，被除数即为结果
    {
        k=n%m;
        n=m;
        m=k;
    }
    a=(b*c)/m;  //公式：最小公倍数=（n*m）/最大公约数
    printf("%ld",m+a);
    return 0;
}

发表于 2022-07-24 10:57:06 回复(0)
C
猪也有猪梦想头像 猪也有猪梦想
#include <stdio.h>
int main()
{
    long a, b;
    long t;
    scanf("%ld %ld", &a, &b);
    long c=a*b;//先把两个数未被改动前的乘积存起来，后面要用到
    while(t=a % b)//辗转相除法
    {
        a = b;
        b = t;
    }//这里已经求出最大公约数b
    printf("%ld\n", (c / b) + b);//两个数的乘积等于这两个数的最大公约数和最小公倍数的积,用两个数的乘积除于最大公约数求出最小公倍数，再加上最大公约数打印
    return 0;
}
发表于 2022-03-24 16:43:08 回复(0)
C
RaiNML头像 RaiNML 
int main()
{
    long long n,m,c;
    scanf("%lld %lld",&n,&m);
    long long x = n * m;
    while(m)
    {
        c = n % m;
        n = m;
        m = c;
    }
    printf("%lld",(x / n) + n);
    return 0;
}

发表于 2022-02-27 15:41:05 回复(0)
C++
virteki73头像 virteki73 
#include <iostream>
using namespace std;
int gcd(int a, int b)
{
    return b? gcd(b, a % b):a;
}

int main()
{
    long long n, m;
    cin >> n >> m;
    long long  a = gcd(n, m);
    long long  b = n * m / a; 
    cout << a + b << endl;
}

发表于 2022-02-26 14:00:04 回复(0)
Java
牛客916830348号头像 牛客916830348号 
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long n = scan.nextLong();
        long m = scan.nextLong();
        long num = n * m;//num：两数乘积
       
        //辗转相除法
        while (m != 0) {
            long tmp = n % m;
            n = m;
            m = tmp;
        }
        //n即两数最大公约数 根据最大公约数和最小公倍数的关系  num / n即最小公倍数
        System.out.println(n + (num / n));
    }
}

发表于 2021-10-25 15:54:32 回复(0)
C
wnlng头像 wnlng
#include<stdio.h>
int main()
{
    long int a,b,t,m,n;
    long long temp,gys,gbs;
    scanf("%ld %ld",&a,&b);
    m=a;
    n=b;
    if(a<b)
    {
        t=a;
        a=b;
        b=t;
    }
    temp=a%b;
    if(temp==0)
        gys=b;
    while(temp!=0) 
    {
        a=b;
        b=temp;
        temp=a%b;
     if(temp==0)
         gys=b;
    }
    gbs=m*n/gys; 
    printf("%lld\n",gbs+gys);
    return 0;
}
发表于 2021-08-12 11:22:13 回复(1)
牛客322840682号头像 牛客322840682号 
#include <stdio.h>
int main()
{    
    long a,b,t,r;
    long su;
    long sum;
    scanf("%ld %ld",&a,&b);
    long n=a*b;
    if(a<b){
        t=b;
        b=a;
        a=t;
    }
    r=a%b;
    while(r!=0)//辗转相除法求最大公约数
    {
        a=b;
        b=r;
        r=a%b;
    }
    su = n/b;/*两个数的积除以最大公约数就是最小公倍数*/
    sum = su + b;
    printf("%ld\n",sum);
    return 0;

}

发表于 2021-05-28 02:51:56 回复(0)
C/C++
已注销头像 已注销 
#include <stdio.h>

void swap(long long int *a, long long int *b);
long long int gcd(long long int x, long long int y);

int main(void)
{
    long long int m, n, r;
    
    while (scanf("%lld %lld", &m, &n) != EOF)
    {
        swap(&m, &n);
        r = gcd(m, n);
        printf("%lld\n", (m * n / r) + r);
    }
    
    return 0;
}

void swap(long long int *a, long long int *b)
{
    if (*a < *b)
    {
        *a ^= *b ^= *a ^= *b;
    }
    return;
}

long long int gcd(long long int x, long long int y)
{
    long long int temp = x % y;
    
    while (temp)
    {
        x = y;
        y = temp;
        temp = x % y;
    }
    return y;
}

发表于 2020-05-02 15:59:27 回复(0)
C
墨染岚音头像 墨染岚音
#include <stdio.h>

long long int GDC(long long int a,long long int b){
    long long int r=a%b;
    while(r!=0){
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}

long long int LDC(long long int a,long long int b){
    long long int r;
    r=GDC(a,b);
    return a/r*b;
}

int main() {
    long long int a, b;
    scanf("%lld %lld",&a,&b);
    if(b>a){
        long long int temp=a;
        a=b;
        b=temp;
    }
    printf("%lld",GDC(a,b)+LDC(a,b));
    return 0;
}
发表于 2025-08-10 09:29:46 回复(0)
_老爹古董店头像 _老爹古董店
#include <stdio.h>

int main() {
    long long int a, b;
    scanf("%lld %lld",&a,&b);
    long long int x=a;
    long long int y=b;
    long long int c=a%b;
    while(c!=0){
        a=b;
        b=c;
        c=a%b;
    }
    long long int m=b;
    long long int n=(x*y)/m;
    long long int sum=m+n;
    printf("%lld",sum);
    return 0;
}
发表于 2024-11-24 11:29:08 回复(0)
反伤%100的冰激凌头像 反伤%100的冰激凌 
int main()
{
	long long n,m = 0;
	scanf("%lld %lld",&n,&m);
	long long a, b, c = 0;
	a = n, b = m;
      //辗转相除法
    // (a、b)的最大公约数 == (b、r)的最大公约数   注：r 为 a / b 的余数
    // 所以不断除下去，直到余数为0，此时的被除数就是原(a、b)的最大公约数
    //
	while (1)
	{
		c = a % b;
		if (c==0)
		{
			break;
		}
		a = b;
		b = c;
	}
    //公式法
    //由于两个数的乘积等于这两个数的最大公约数与最小公倍数的积。
    //即（a，b）×[a，b]=a×b。所以，求两个数的最小公倍数，
    //就可以先求出它们的最大公约数，然后用上述公式求出它们的最小公倍数。
	c = (n * m) / b;
	printf("%lld",b+c);


	return 0;
}

发表于 2024-07-31 08:05:45 回复(0)
C
区欠阳头像 区欠阳 
#include <stdio.h>
int main() 
{
    // 定义变量
    long long int a = 0;
    long long int b = 0;
    // 输入
    scanf("%lld %lld",&a, &b);
    // 先保存a*b,因为我们找到a*b就是他们两个最大公约数和最小公倍数之和
    long long int l = a*b;
    // 辗转相除法算出最大公约数
    long long int c = 0;
    while(a%b!=0)
    {
        c=a%b;
        a=b;
        b=c;
    }
    // 判断c是否为0，可能会出现求10和10这种情况，c为0，我们不可以出现除以0的情况
    if(c)
    {
        long long int w = (l)/c;
        printf("%lld",w+c);
    }
    else {
        long long int w = l/a;
        printf("%lld",w+a);
    }
        return 0;
}


编辑于 2024-04-14 16:50:41 回复(0)
提交观点

问题信息

上传者：牛客309119号
难度：
136条回答 3852浏览

热门推荐

通过挑战的用户

查看代码

相关试题

小乐乐与欧几里得

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号