首页 › 题库 › GESP编程能力等级认证 › 1.2 最大公约数与最小公倍数

GESP-C++五级 题库

共 14 道题 · 按题型筛选,点「查看答案」核对解析
章节 1.2 最大公约数与最小公倍数 清除

下面代码实现了欧几里得算法。下面有关说法,错误的是( )。

int gcd1(int a, int b) { 
    return b == 0 ? a : gcd1(b, a % b); 
} 
int gcd2(int a, int b) { 
    while (b != 0) { 
        int temp = b; 
        b = a % b; 
        a = temp; 
    } 
    return a; 
}
A
gcd1() 实现为递归方式。
B
gcd2() 实现为迭代方式。
C
当 a较大时, gcd1() 实现会多次调用自身,需要较多额外的辅助空间。
D
当 a较大时, gcd1() 的实现比 gcd2() 执行效率更高。
答案与解析
正确答案:D
分析两个函数的实现结构:gcd1使用函数调用自身的方式,每次传入参数b和a对b取模的结果,直到b为0时返回a;递归过程中每层调用均需保存执行上下文。gcd2通过循环更新变量a和b的值,其中b被赋为a % b,a被赋为原b的值,循环持续到b为0为止;整个过程仅使用固定数量的局部变量。比较两者在控制流机制上的差异,递归版本依赖调用栈传递状态,迭代版本通过变量重用维护状态。
题目详情

以下代码计算两个正整数的最大公约数(GCD),横线上应填写( )

A

b

B

a

C

temp

D

a * b

答案与解析
正确答案:B
这道题暂未补解析。
题目详情

下列C++代码用两种方式求解两个正整数的最大公约数,说法【错误】的是?( )

int gcd0(int big, int small) {
    if (big < small) {
        swap(big, small);
    }
    if (big % small == 0) {
        return small;
    }
    return gcd0(small, big % small);
}
int gcd1(int big, int small) {
    if (big < small) {
        swap(big, small);
    }
    for (int i = small; i >= 1; --i) {
        if (big % i == 0 && small % i == 0)
            return i;
    }
    return 1;
}
A
gcd0() 函数的时间复杂度为 O(log n)
B
gcd1() 函数的时间复杂度为 O(n)
C
一般说来, gcd0() 的效率高于 gcd1()
D
gcd1() 中的代码 for (int i = small; i >= 1; --i) 应该修改为 for (int i = small; i > 1; --i)
答案与解析
正确答案:D
这道题暂未补解析。
题目详情

用以下辗转相除法(欧几里得算法)求gcd(84, 60)的步骤中,第二步计算的数是?( )

int gcd(int a, int b) {
    int big = a > b ? a : b;
    int small = a < b ? a : b;
    if (big % small == 0) {
        return small;
    }
    return gcd(small, big % small);
}
A
84和60
B
60和24
C
24和12
D
12和0
答案与解析
正确答案:B

调用gcd(84, 60)函数中:

big=84,small=60,big % small不为零,递归调用:

gcd(60, 24)。

题目详情

两块长方形土地的长宽分别为 24 和 36 米,要将它们分成正方形的小块,使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24, 36) 来求正方形分块的边长,则函数 gcd 调用顺序为( )。

int gcd(int a, int b) {
	int big = a > b ? a : b;
	int small = a < b ? a : b;
	if (big % small == 0) {
		return small;
	}
	return gcd(small, big % small);
}
A
gcd(24, 36)、gcd(24, 12)、gcd(12, 0)
B
gcd(24, 36)、gcd(12, 24)、gcd(0, 12)
C
gcd(24, 36)、gcd(24, 12)
D
gcd(24, 36)、gcd(12, 24)
答案与解析
正确答案:C
这道题暂未补解析。
题目详情

下面是根据欧几里得算法编写的函数,它计算的是 与 的( )。

int gcd(int a, int b) {
	while (b != 0) {
		int temp = b;
		b = a % b;
		a = temp;
	}
	return a;
}
A
最小公倍数
B
最大公共质因子
C
最大公约数
D
最小公共质因子
答案与解析
正确答案:C

欧几里得算法,也称为辗转相除法,用于计算两个非负整数的最大公约数。

在函数中,通过循环不断将b 更新为a 除以b 的余数,直到b 变为0。此时a 的值就是最大公约数。

函数最终返回的是变量a 的值,即为输入的两个整数a 和b 的最大公约数。

因此,根据给出的函数实现和算法特性,函数gcd(int a, int b) 计算的是两个整数的最大公约数。

所以,答案是C.最大公约数。

题目详情

欧几里得算法还可以写成如下形式:

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

下面有关说法,错误的是( )。

A
本题的 gcd() 实现为递归方式。
B
本题的 gcd() 代码量少,更容易理解其辗转相除的思想。
C
当a较大时,本题的 gcd() 实现会多次调用自身,需要较多额外的辅助空间。
D
当a较大时,相比上题中的 gcd() 的实现,本题的 gcd() 执行效率更高。
答案与解析
正确答案:D

递归实现的gcd()函数并不比非递归实现的效率更高。两者的时间复杂度是相同的,选择使用哪种实现通常更依赖于个人或特定环境下的偏好或要求。

题目详情

辗转相除法也被称为(   )

A
高斯消元法
B
费马定理
C
欧几里德算法
D
牛顿迭代法
答案与解析
正确答案:C
这道题暂未补解析。
题目详情

假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm(a,b) 函数能正确找到两个正整数 a 和 b 的最小公倍数。

int lcm(int a, int b) { 
    return a / gcd(a, b) * b; 
}


A
对
B
错
答案与解析
正确答案:对
分析函数 lcm(a, b) 的表达式结构,观察其运算顺序与数学关系。确认 a 和 b 是否通过 gcd(a, b) 进行整除操作,并判断该操作是否在整数除法下保持精度。检查表达式 a / gcd(a, b) * b 是否等价于 (a * b) / gcd(a, b) 的数学变换形式。验证该计算过程是否符合最小公倍数的定义,即能被 a 和 b 整除的最小正整数。考虑整数溢出与除法截断对结果的影响,分析运算顺序对中间结果的影响。
题目详情

假设函数 gcd() 能正确求两个正整数的最大公约数,则下面的 findMusicalPattern(4,6) 函数返回2。

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情

下面C++代码是用欧几里得算法(辗转相除法)求两个正整数的最大公约数, a 大于 b 还是小于 b 都适用。( )

int gcd(int a, int b) {
    while (b) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情

假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm() 函数能求相应两数的最小公倍数。( )

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情

辗转相除法用于求两个整数的最大公约数。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情

最大公因数

时间限制:1 s,内存限制:512 MB

【问题描述】

对于两个正整数 a、b,它们的最大公因数记为 gcd(a, b)。对于 k >=3 个正整数 c1、c2、……、ck,它们的最大公因数为:

gcd(c1, c2, ……, ck) = gcd(gcd(c1, c2, ……, c(k-1), ck)

给定 n 个正整数 a1、a2、……、an 以及 q 组询问。对于第 i(1<=i<=q)组询问,请求出 a1+i、a2+i、……、an+i 的最大公因数,也即 gcd(a1+i, a2+i, …… , an+i)。

【输入描述】

第一行,两个正整数 n、q,分别表示给定正整数的数量,以及询问组数。

第二行, n 个正整数 a1、a2、……、an。

【输出描述】

输出共 q 行,第 i 行包含一个正整数,表示 a1+i、a2+i、……、an+i  的最大公因数。

【样例输入1】

5 3
6 9 12 18 30

【样例输出1】

1
1
3

【样例输入2】

3 5
31 47 59

【样例输出2】

4
1
2
1
4

【数据范围】

对于60%的测试点,保证 1 <= n <= 1000,1 <= q <= 10。

对于所有测试点,保证 1 <= n、q <= 10^5,1 <= ai <= 1000。

答案与解析
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n, q, a[N], g;
int gcd(int a, int b) {
    if (a == 0 || b == 0)
        return a + b;
    return gcd(b, a % b);
}
int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    for (int i = 2; i <= n; i++)
        g = gcd(g, a[i] - a[i - 1]);
    for (int i = 1; i <= q; i++)
        cout << gcd(g, a[1] + i) << endl;
    return 0;
}
题目详情