首页 > 试题广场 >

小乐乐与欧几里得

[编程题]小乐乐与欧几里得
  • 热度指数：69255 时间限制：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
算法知识视频讲解
添加回答
C
牛客322294286号头像 牛客322294286号
#include <stdio.h>

int main() {
    long int m,n,max,min,k;
    scanf("%ld %ld",&m,&n);
    k=m*n;
    while(m&&n)
    {
        if(m>n){
            m%=n;
        }
        else{
            n%=m;
        }
    }
    max=m>n?m:n;
    min=k/max;
    printf("%ld",max+min);
    return 0;
}
发表于 2024-10-15 09:26:45 回复(0)
C
Anout头像 Anout 
#include <stdio.h>

//辗转相除法
long gcd(long a, long b) {
    while (a % b) {
        long c = a % b;
        a = b;
        b = c;
    }
    return b;
}

//两数的乘积再除以两数的最大公约数法
long lcm(long a, long b, long c) {
    return a * b / c;
}

int main() {
    long a, b;
    while (scanf("%ld %ld", &a, &b) != EOF) {
        long max = gcd(a, b);
        long min = lcm(a, b, max);
        printf("%ld\n", max + min);
    }
    return 0;
}


发表于 2024-08-24 11:20:35 回复(0)
C
佰木BM头像 佰木BM
#include<stdio.h>
int main()
{
    long long int a = 0, b = 0, c =0;
    long long int m=0,n=0;
    scanf("%d %d", &a,&b);
    m=a;n=b;
    if(a<b)
    {
        c = a;   a = b; b = c;
    }

    c = 1;
    while (c!= 0)
    {
        c = (a%b);
        a = b;
        b = c;

    }
long long  minmlt=(m*n)/a;
    printf("%lld",minmlt+a);

    return 0;
}
发表于 2024-07-30 11:18:49 回复(0)
C
爱喝奶茶的熊猫觉醒了头像 爱喝奶茶的熊猫觉醒了
#include<stdio.h>

int main(){
    int a,b,i=0,j,rest,num;
    scanf("%d %d",&a,&b);
    i = (a>b)?b:a;
    //printf("%d\n",i);
    for(j=i;j>1;j--){  
        if((a%j==0) && (b%j==0)){
            //printf("%d\n",j);
            rest = a * b / j;
            //printf("%d",rest);
            num = rest + j;
            printf("%d",num);            
            break;
        }
    }
    return 0;

}

发表于 2024-06-17 18:04:28 回复(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)
C
徐文达头像 徐文达 
#include <stdio.h>

long long  Max_divisor(int a, int b)
{
	int c = 0;
	
	//辗转相除法
	// (a、b)的最大公约数 == (b、r)的最大公约数   注：r 为 a / b 的余数
	// 所以不断除下去，直到余数为0，此时的被除数就是原(a、b)的最大公约数
	//
	while (c = a % b)
	{
		a = b;
		b = c;
	}
	return b;
}

long long  Min_multiple(int n, int m)
{
	return (long long )n*m/Max_divisor(n, m);
}

int main()
{
	int n = 0;
	int m = 0;
	long long sum = 0;

	scanf("%d %d", &n, &m);


	//最大公约数
	sum += Max_divisor(n, m);

	//最小公倍数
	sum += Min_multiple(n, m);

	printf("%lld\n", sum);

	return 0;
}

编辑于 2024-02-06 17:31:10 回复(0)
C
悟了一个空头像 悟了一个空
#include <stdio.h>
long gcd(long a,long b){
    if(b==0){
        return a;
    }
    else return gcd(b,a%b);
}
int main() {
    long a, b,c,d,s;
    scanf("%ld %ld",&a,&b);
    c=gcd(a,b);//c存最大公约数
    d=a/c*b;//d存最小公倍数
    s=c+d;
    printf("%ld",s);
    return 0;
}
编辑于 2024-01-06 14:45:11 回复(0)
C
yangwy头像 yangwy
#include <stdio.h>

int main() {
    long n, m, a, b, Y, y;
    scanf("%ld %ld", &n, &m);
    if(n>m){
        a=n;
        b=m;
    }
    else{
        a=m;
        b=n;
    }
    Y = b;
    while(Y){
        Y = a % Y;
        a = b;
        b = Y;
    }
    printf("%ld", a + n*m/a);
    return 0;
}
编辑于 2024-01-03 12:23:14 回复(0)
C
牛客101757373号头像 牛客101757373号 
int main()
{
	long x, y;
	long r = 0;
	scanf("%ld %ld", &x, &y);

	int max = x > y ? x : y;
	int min = x < y ? x : y;

	while (r = max % min)
	{
		max = min;
		min = r;
	}

	printf("%ld", x * y / min + min);


	return 0;
}

发表于 2023-11-22 19:33:45 回复(0)
C
彩妙不是菜喵头像 彩妙不是菜喵 
#include <stdio.h>
//调试中数值过大  所以整型为long long

long long funny(long long a,long long b){
    long long i;
    while((i=a%b)!=0){
        a=b;
        b=i;
    }
    return b;
}
//辗转相除求最大公约数 b
long long fummin(long long a,long long b){
    long long min;
    min=(a*b)/funny(a,b);//最小公倍数=两数之积除以最大公约数
return min;
}
//最小公倍数
int main() {
    long long i,j,n,k,m;
    scanf("%lld %lld",&m,&n);
    i=funny(m,n);
    j=fummin(m,n);
    k=i+j;
    printf("%lld\n",k);
    return 0;
}

发表于 2023-10-28 21:27:01 回复(0)
C
这道题不会解呀头像 这道题不会解呀 
#include <stdio.h>

int main()
{
    long long n = 0, m = 0;   //给两个整数
    long long ret = 1;        //辗转相除发求最大公约数
    long long num = 0;        //存放两个整数相乘的值
    long long g = 0;          //存放最小公倍数
    scanf("%lld %lld", &n, &m);
    num = n * m;

    while ((ret = n % m) != 0)          //当ret=0时跳出循环
    {
        //辗转相除法求最大公约数，当ret=0时m就是最大公约数
        n = m;
        m = ret;       //m就是最大公约数
    }

    g = num / m;        //两整数的乘积=两个整数的 最大公因数×最小公倍数

    printf("%lld", g + m);

    return 0;
}

发表于 2023-10-23 17:15:13 回复(0)
C
牛客33774771号头像 牛客33774771号 
int main() {
    long long a = 0;
    long long b = 0;
    long long max = 0;
    long long zuixiaogongbeishu = 0;
    scanf("%lld %lld", &a, &b);
    max = a * b;
    while (a != b) {
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    }
    zuixiaogongbeishu = max / a;
    printf("%lld", a + zuixiaogongbeishu);
    return 0;
}

发表于 2023-10-23 11:37:39 回复(0)
C
牛客937772635号头像 牛客937772635号
#include <stdio.h>

int main() {
    long long  n, m, c,d,e,sum;
    scanf("%lld %lld",&n,&m);
    if (n < m)//确保大数放在n中
        {
            long long tmp = m;
            m = n;
            n = tmp;
        }
    c=n%m;
    d=n;
    e=m;
    if(c==0&&n!=m)
    {
        printf("%lld",d+e);
    }
     while(c!=0)
     {
        d=e;
        e=c;
        c=d%e;
     }
     long long  i=n/e;
     sum=e+m*i;
    printf("%lld",sum);
    return 0;
}
发表于 2023-10-20 19:25:12 回复(0)
C
樗蚕头像 樗蚕
#include <stdio.h>

int main() {
    int a, b,c,d,i,j;
    scanf("%d %d",&a,&b);
    if(a>b)
    {
        i=a;
        j=b;
    }
    else
    {
        i=b;
        j=a;
    }
    for(;;i++)
    {
      if(i%a==0&&i%b==0)
      {
        c=i;
        break;
      }
    }
    for(;j>0;j--)
    {
        if(a%j==0&&b%j==0)
        {
            d=j;
            break;
        }
    }
    printf("%d",c+d);
    return 0;
}
发表于 2023-10-07 00:52:28 回复(2)
C
牛客843392233号头像 牛客843392233号
#include <stdio.h>

int main() {
    long long n,m;
    scanf("%lld%lld",&n,&m);
    long long gcd=1;
    long long n1=n,m1=m;
    //把奇数偶数分离了,可以写在一起的
    while((n1%2==0)&&(m1%2==0)){
        if((n1%2==0)&&(m1%2==0)){
            n1/=2;
            m1/=2;
            gcd=gcd*2;
        }
    }
    for(int i=2;(2*i-1)<=n1&&(2*i-1)<=m1;i++){int k1=0;int k2=-1;int j=2*i-1;
        if(n1%j==0){k1=1;n1/=j;}
        if(m1%j==0){k2=1;m1/=j;}
        if(k1==k2){gcd=gcd*j;i=2;}
    }
    //printf("%lld\n",gcd);
    long  long lcm;
    lcm=n*m/gcd;
    printf("%lld",gcd+lcm);
    return 0;
}
发表于 2023-09-28 09:55:28 回复(0)
C
YyRan头像 YyRan
#include <stdio.h>
typedef unsigned long long u_l_l;

int main() {
    u_l_l i = 0;
    u_l_l j = 0;
    u_l_l k = 0;
    scanf("%llu %llu", &i, &j);
    u_l_l max = i > j ? i : j;
    u_l_l min = i < j ? i : j;
    k = max % min;
    if(k != 0)
    {
        while(1)
        {
            max = min;
            min = k;
            k = max % min;
            if(k == 0)
                break;
        }
    }
    else
    {
        min = i;
    }
    u_l_l yue = min;
    u_l_l bei = i * j / yue;
    u_l_l sum = yue + bei;
    printf("%llu", sum);

    return 0;
}
发表于 2023-02-25 16:08:10 回复(0)
C
小狗汪叽头像 小狗汪叽 
// 短除法
#include <stdio.h>
typedef long long int_64;
int_64 getGreatestComDiv(int_64 x, int_64 y);
int_64 getLeastComMul(int_64 x, int_64 y, int_64 (*pf)(int_64, int_64));

int main() {
    // enter two numbers
    int_64 a, b;
    scanf("%lld %lld", &a, &b);
    printf("%lld\n", getGreatestComDiv(a, b) + getLeastComMul(a, b,
            &getGreatestComDiv));

    return 0;
}

int_64 getGreatestComDiv(int_64 x, int_64 y) {
    int_64 result = 1, i = 2, temp;

    // To confirm the larger number, select y to be the larger one.
    if (x > y) {
        temp = x;
        x = y;
        y = temp;
    }

    // Check for the greatest common divisor by while-loop
    while (i <= x) {
        // To make sure i is a common divisor of both two numbers
        if ((x % i == 0) && (y % i == 0)) {
            x /= i; // Keep the value of x to next loop
            y /= i; // Keep the value of y to next loop
            result *= i;
            i = 2;
        } else {
            i++;
        }

    }
    return result;
}

int_64 getLeastComMul(int_64 x, int_64 y, int_64 (*pf)(int_64, int_64)) {
    int_64 result;
    result = (x * y) / pf(x, y);
    return result;
}

发表于 2023-01-31 09:17:51 回复(1)
C
牛客805839823号头像 牛客805839823号 
#include <stdio.h>
int main() {
    long long n = 0, m = 0;
    scanf("%lld %lld", &n, &m);
    long long oldn = n, oldm = m;;
    long long sum = 1;
    while (sum = (n % m)) {
        n = m;
        m = sum;
    }
    // int i = 1;
    // for (i = 1;; i++) {
    //     if (i * oldn % oldm == 0) {
    //         break;
    //     }
    // }
    printf("%lld", m +(oldn*oldm)/m);
}

发表于 2022-10-23 22:19:40 回复(0)
提交观点

问题信息

上传者：牛客309119号
难度：
42条回答 2739浏览

热门推荐

通过挑战的用户

查看代码

相关试题

小乐乐与欧几里得

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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