首页 > 试题广场 >

最大公约数

[编程题]最大公约数

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

小易学习了辗转相除法之后，就开始实践这个算法在求解最大公约数上。

牛牛给小易出了一道不同寻常的求解最大公约数: 求解a和b的最大公约数，但是a和b的范围特别大。

小易遇到了困难，向聪明的你寻求帮助，希望你能帮帮他。

输入描述:

第一行数字a，第二行数字b。

输出描述:

一行一个数字表示答案

示例1

输入

6
4

输出

示例2

输入

7951346523609888
6998915114363550

输出

算法知识视频讲解

FengxiuLi

//我看到没有人使用JS做，我来解决一下
let bfc = (a, b) => {
	if (b === 0) {
		return a
	} else {
		return bfc(b, parseInt(a % b))
	}
}
console.log(bfc(9, 6))

发表于 2020-04-11 16:24:52 回复(0)

gogogoovo

C++

#include <iostream>
#include <string>
using namespace std;

long long gcd(long long a, long long b) {//辗转相除
   if (b == 0) return a;
   return gcd(b, a%b);
}

int main() {
   string s;
   getline(cin,s);
   long long a = 0, b;
   cin >> b;
   for (int i = 0; s[i] != '\0'; i++) {
      a = (a * 10 + s[i] - '0') % b;
   }//先用最大值除以最小值得到一个较小的数防止数据溢出
   cout << gcd(a, b);
   return 0;
}

编辑于 2020-05-14 15:45:40 回复(0)

孝陵卫的风

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.nextLine();
        long b = scanner.nextLong();
        //将这里返回的ans与b求最大公约数即可
        long ans = demo2(a, b);
        if (ans == 0) {
            System.out.println(b);
            return;
        }
        System.out.println(gcd(ans, b));
    }

    //将第一个很大的数long类型装不下，需要按位处理，
    public static long demo2(String a, long b) {
        //余数
        long remainder = 0;
        //从最高位开始取一位与被除数
        for (int i = 0; i < a.length(); i++) {
            remainder = remainder * 10 + a.charAt(i) - '0';
            remainder %= b;
        }
        return remainder;
    }

    //求最大公约数
    public static long gcd(long minNum, long maxNum) {
        //确保第一个数小于第二个数
        if (minNum > maxNum) {
            long remp = minNum;
            minNum = maxNum;
            maxNum = minNum;
        }
        long remainder = 1;
        //用于保存结果
        long result = 0;
        while (remainder != 0) {
            result = minNum;
            remainder = maxNum % minNum;
            maxNum = minNum;
            minNum = remainder;
        }
        return result;
    }
}

编辑于 2020-04-06 23:20:05 回复(0)

牛客864355626号

def hcf(a, b):
    a, b = min(a, b), max(a, b)
    if b % a == 0:
        return a
    else:
        return hcf(a, b % a)

a = int(input())
b = int(input())
print(hcf(a, b))

发表于 2020-01-03 17:54:37 回复(0)

Python

gerizeman

a_temp = int(input())
b_temp = int(input())

a = max(a_temp, b_temp)
b = min(a_temp, b_temp)

while a % b != 0:
    temp = a % b
    a = b
    b = temp

print(b)

编辑于 2020-04-10 23:31:34 回复(2)

Java

杰锅

import java.util.*;
import java.math.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            BigInteger a = sc.nextBigInteger();
            BigInteger b = sc.nextBigInteger();
            System.out.println(a.gcd(b));
        }
    }
}

发表于 2020-01-11 23:22:36 回复(0)

牛客36216917号

import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static BigInteger gcd(BigInteger m, BigInteger n) {
BigInteger temp;
while (n.compareTo(BigInteger.ZERO)!=0) {
temp = m.remainder(n);
m = n;
n=temp;
}
return m;
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
BigInteger a = in.nextBigInteger();
BigInteger b = in.nextBigInteger();
System.out.print(gcd(a, b));
}

}

发表于 2023-08-18 16:31:07 回复(0)

Javascript_V8

i671

Js过不了啊，超时？

发表于 2022-01-16 18:39:49 回复(0)

有点饿

def fun(a,b):
a,b = min(a,b), max(a,b)
if b%a == 0: #余数为0
return a
else:
return fun(a, b%a)

a = int(input('please input a：'))
b = int(input('please input b：'))
print(fun(a, b))

发表于 2022-01-14 18:14:00 回复(0)

Dame、CX

print('请输入a的值:')
a = int(input())
print('请输入b的值:')
b = int(input())
s = []
n = min(a,b)
for i in range(1,n+1,1):
    if a%i == 0 and b%i == 0 :
        s.append(i)
print('a和b的最大公约数为:',max(s))

发表于 2021-07-29 13:44:23 回复(0)

YHSSSS

import java.math.BigDecimal;
import java.util.*;

public class test9{
    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        BigDecimal a = new BigDecimal(sc.nextLine());
        BigDecimal b = new BigDecimal(sc.nextLine());

        BigDecimal temp = a;
  
        do{
            temp = a.divideAndRemainder(b)[1];
            a = b;
            b = temp;
        }while(temp.longValue() != 0);
            
        System.out.println(a.longValue());

        sc.close();
    }
}

发表于 2020-08-12 14:08:15 回复(0)

牛客951427206号

可以再简化一下，不用判断a,b大小

def hcf(a, b):
    #a, b = min(a, b), max(a, b)
    if b % a == 0:
        return a
    else:
        return hcf( b%a, a)

a = int(input())
b = int(input())
print(hcf(a, b))

当a>b时在第一次调用时就会交换a,b的值，因为此时 b % a == b ，所以hcf(b%a,a)等价于hcf(b,a)

发表于 2020-08-08 03:08:32 回复(0)

Python

未来数据分析师

import numpy as np
a_temp = int(input())
b_temp = int(input())
a = max(a_temp, b_temp)
b = min(a_temp, b_temp) while np.mod(a,b) != 0:
    temp = a % b
    a = b
    b = temp  print(b)

想请问大家为什么用numpy之后报错呢？错误信息是：请检查是否存在语法错误或者数组越界非法访问等情况

把np.mod(a, b) 换成 a%b 就可以通过。有人知道原因吗？

编辑于 2020-07-23 21:38:21 回复(0)

牛客188000430号

#include<iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    int res=1;
    while(res)
    {
        res=a%b;
        a=b;
        b=res;
    }
    cout<<a;
}

就想知道我哪错了哦！为啥只能通过30%？

发表于 2020-06-29 22:40:40 回复(1)

FairyTale⚖

def fun(x, y):
    a = max(x, y)
    b = min(x, y) 
    if a % b == 0: 
        return b 
    else: 
        return fun(b, a % b)   # 为啥去除这个return就不完全对呢？没想明白

a = int(input())
b = int(input()) 
print(fun(a,b))

发表于 2020-03-04 20:12:08 回复(2)

生活不易，offer来碗里

function maxg (a,b){
   x = Math.max(a,b);
   y = Math.min(a,b)
   if(x % y == 0){
   return y
   }else{
   return maxg(x,x%y);
   }

}

发表于 2020-03-01 17:22:30 回复(2)

巴别塔底的夏虫

def f(a, b):

while a != b:

if a > b:

a -= b

else:

b -= a

return a

发表于 2019-12-03 23:19:34 回复(0)

提交观点

问题信息

C++工程师前端工程师网易 2020 大数据开发工程师数据分析师 Java工程师

上传者：小小

难度：

17条回答 148收藏 6828浏览

通过挑战的用户

SEHOD

2023-02-01 18:45:27
一衬黑衣

2022-11-01 19:14:30
愤怒的他说等下...

2022-10-12 15:26:47
牛客51896...

2022-10-05 18:03:50
漠筱九

2022-09-25 15:09:33

最大公约数

输入描述:

输出描述:

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题