小乐乐与欧几里得_

梦想还是要有的丶

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

记录一下。

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号

#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

求最大公约数常用的有两种方法，一是九章算术中的更相减损术：大数减小数直到相等，相等的数即最大公约数，该算法时间复杂度约为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

#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.白

#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

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

#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号

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

#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号

#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)

反伤%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)

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++

mrcuihao

#include <iostream>
using namespace std;

long int maxCommonFactor(long int n, long int m) {
    if (n < m) {
        int temp = n;
        n = m;
        m = temp;
    }
    while (n % m) {
        int temp = n % m;
        n = m;
        m = temp;
    }
    return m;
}

int main() {
    long int n, m, min;
    cin >> n >> m;
    min = maxCommonFactor(n, m);
    cout << min + (n * m) / min;
    return 0;
}

发表于 2022-07-19 15:11:36 回复(0)

小乐乐与欧几里得

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题