数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学查找指定范围内的最大公约数 (GCD)
问题要求我们找到位于给定范围内的最大公约数 (GCD)。我们将得到两个正整数 x 和 y，以及两个整数 p 和 q，它们表示范围 [p,q]。我们需要找出 x 和 y 的最大公约数，并且这个最大公约数必须落在这个范围 [p,q] 内。最大公约数 (GCD)，在数学中也称为最大公因数，是能够同时整除两个给定正整数的最大正整数。给定的整数不能为零。对于任意两个正整数 x 和 y，它表示为 gcd(x,y)。
例如，我们得到两个正整数 6 和 9。它们的最大公约数 gcd(6,9) 为 3，因为它是能够同时整除这两个数的最大数。
但是在这个问题中，我们需要找到两个给定正整数的最大公约数，并且这个最大公约数必须落在指定的范围内。让我们用例子来理解这个问题。我们将得到 4 个数字作为输入：x 和 y（用于求这两个数的最大公约数），以及两个数字表示最大公约数的范围，即 [p,q]。
输入：x=8，y=12，p=1，q=3
输出 : 2
解释 – 给定两个数 x 和 y 的最大公约数是 4。但是 4 不在范围 [1,3] 内。在这个范围内最大的公约数是 2，这就是我们需要的输出。
输入：x=17，y=15，a=5，b=10
输出 : -1
解释 – 数 17 和 15 的最大公约数是 1。由于 1 不在给定范围 [5,10] 内。当给定范围内没有公约数时，我们需要输出 -1。
算法
我们将用来解决这个问题的算法非常简单，并且与数学相关。首先，我们将找到数 x 和 y 的最大公约数 (GCD)。在 C++ 中，有一个名为 gcd() 的内置函数，它返回两个数的最大公约数作为输出。
语法
int divisor=gcd(x,y);
我们也可以使用高效的欧几里得算法来查找两个数的最大公约数。两者的时间复杂度相同，即 O(log(min(x,y)))。
现在，我们可以根据简单的算术定律得出结论：能够整除两个数的最大公约数的数，也能同时整除这两个数本身。因此，从 i=1 迭代到 sqrt(gcd(x,y)) 将帮助我们获得该数的所有公约数。
然后，检查从 1 到 sqrt(gcd(x,y)) 的每一个 i 是否整除 gcd(x,y)。如果 i 整除 gcd(x,y)，那么我们可以说 gcd(x,y)/i 也是 gcd 的约数，因此它也是数 x 和 y 的公约数。
让我们用一个例子来理解这个概念。假设 x 和 y 为 32 和 48。gcd(18,27) 为 16。在这种情况下，我们将从 i=1 迭代到 i<=4，即 sqrt(16)。让我们考虑 i=2。这里 i 整除 gcd(18,27)，即 16/2 等于 8。因此，gcd(x,y)/i 也将整除 gcd(x,y) 得到 i。
注意 – 如果一个数 n 除以任何数 x 得到 y，可以表示为 $\frac{n}{x}\:=\:y$，那么 y 也将整除 n 得到 x $(x\:\times\:y\:=\:n)$。
这个算法可能是解决这个问题最有效的方法。遵循此算法时，我们将不断检查公约数是否在范围 [a,b] 内。如果在范围内，我们将使用 **max()** 函数在一个变量中更新约数，以便获得范围内最大的公约数。
max() 函数的语法
int m = max(a,b);
它返回 a 和 b 中较大的值。
方法
以下是我们将遵循的方法：
初始化一个函数来计算位于给定范围内的最大公约数。
计算两个给定正数 x 和 y 的最大公约数。
初始化一个名为 ans 的变量，其值为 -1。
从 i=1 迭代到 i<=sqrt(gcd(x,y))，并不断检查 i 是否整除 gcd(x,y)。
如果 (gcd(x,y)%i)=0，则检查 i 是否在范围 [a,b] 内，如果在范围内，则使用 max() 函数将其存储在 ans 中，以便我们获得范围内最大的公约数。
还要检查 gcd/i 是否在范围内，如果在范围内，则再次使用 max() 函数更新 ans 的值。
完成 for 循环中的所有迭代后返回 ans。
示例
C++ 中该方法的实现：
#include<stdio.h>
#include<bits/stdc++.h>
using namespace std;
// to calculate gcd of two numbers using Euclidean algorithm
int gcd(int a, int b){
if(a == 0)
return b;
return gcd(b % a, a);
}
//function to calculate greatest common divisor in the given range [a,b]
int build(int x, int y, int a, int b) {
//using C++ inbuilt library to calculate gcd of given numbers
int z = gcd(x, y); //we can use euclidean algorithm too as an alternative
int ans = -1; //storing -1 for the case when no common divisor lies in the range
for(int i = 1; i<=sqrt(z); i++) { //iterating until sqrt(z) because either of two factors
//of a number must be less than square root of the number
if(z % i == 0) {
if(i >= a && i <= b) //checking it i lies in the range
ans = max(ans, i); //storing maximum value
if((z / i) >= a && (z / i) <= b)
ans = max(ans, z / i);
}
}
return ans;
}
int main() {
int x, y, a, b;
x=24, y=42, a=3, b=9;
cout << build(x, y, a, b) <<" is the gcd that lies in range ["<<a<<","<<b<<"]"<<endl;
return 0;
}
输出
6 is the gcd that lies in range [3,9]
时间复杂度：O(log(min(x,y)) + sqrt(z))，其中 z 是两个数 x 和 y 的最大公约数。
空间复杂度：O(1)，因为没有使用额外的空间。
结论
我们讨论了解决问题的方法，即查找位于范围 [a,b] 内的两个数的最大公约数。这就是我们如何使用各种不同函数在 C++ 中解决上述问题。
我希望您觉得这篇文章有帮助，并能清除您对该问题的全部概念。
479 次浏览
