GESP-C++五级 题库
下面代码实现了欧几里得算法。下面有关说法,错误的是( )。
下列C++代码用两种方式求解两个正整数的最大公约数,说法【错误】的是?( )
用以下辗转相除法(欧几里得算法)求gcd(84, 60)的步骤中,第二步计算的数是?( )
调用gcd(84, 60)函数中:
big=84,small=60,big % small不为零,递归调用:
gcd(60, 24)。
两块长方形土地的长宽分别为 24 和 36 米,要将它们分成正方形的小块,使得正方形的尺寸尽可能大。小杨采用如下的辗转相除函数 gcd(24, 36) 来求正方形分块的边长,则函数 gcd 调用顺序为( )。
下面是根据欧几里得算法编写的函数,它计算的是 与 的( )。
欧几里得算法,也称为辗转相除法,用于计算两个非负整数的最大公约数。
在函数中,通过循环不断将b 更新为a 除以b 的余数,直到b 变为0。此时a 的值就是最大公约数。
函数最终返回的是变量a 的值,即为输入的两个整数a 和b 的最大公约数。
因此,根据给出的函数实现和算法特性,函数gcd(int a, int b) 计算的是两个整数的最大公约数。
所以,答案是C.最大公约数。
欧几里得算法还可以写成如下形式:
下面有关说法,错误的是( )。
递归实现的gcd()函数并不比非递归实现的效率更高。两者的时间复杂度是相同的,选择使用哪种实现通常更依赖于个人或特定环境下的偏好或要求。
假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm(a,b) 函数能正确找到两个正整数 a 和 b 的最小公倍数。
假设函数 gcd() 能正确求两个正整数的最大公约数,则下面的 findMusicalPattern(4,6) 函数返回2。

下面C++代码是用欧几里得算法(辗转相除法)求两个正整数的最大公约数, a 大于 b 还是小于 b 都适用。( )
假设函数 gcd() 函数能正确求两个正整数的最大公约数,则下面的 lcm() 函数能求相应两数的最小公倍数。( )
最大公因数
时间限制: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】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于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;
}