目录
算法
语法
max() 函数的语法
方法
示例
输出
结论
首页 后端开发 C++ 找到给定范围内的最大公约数

找到给定范围内的最大公约数

Aug 28, 2023 pm 02:28 PM
范围 最大公约数

找到给定范围内的最大公约数

问题表明我们需要找到给定范围内的 GCD。我们将得到两个正整数 x 和 y 以及两个整数 p 和 q,其范围为 [p,q]。我们需要找出落在 [p,q] 范围内的数字 x 和 y 的 GCD(最大公约数)。 GCD,在数学中被称为最大公约数,是两个给定正整数相除的最大正整数。给定的整数不得为零。对于任意两个正整数 x 和 y,它表示为 gcd(x,y)。

例如,我们有两个正整数 6 和 9。最大公约数 gcd(6,9) 将为 3,因为它是除以这两个数字的最大数。

但是在这个问题中,我们需要找到两个给定的在指定范围内的正整数的最大公约数。让我们通过例子来理解这个问题。我们将得到 4 个数字作为输入 x 和 y 来查找这些数字的 gcd 和两个指示 gcd 范围的数字,即 [p,q]。

输入:x=8、y=12、p=1、q=3

输出:2

解释 - 由于给定的两个数字 x 和 y 的最大公约数是 4。但是 4 不在范围 [1,3] 之内。 [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);
登录后复制

我们还可以使用欧几里得算法的有效方法来查找两个数字的 gcd。两者同时工作,时间复杂度为 O(log(min(x,y))。

现在,我们可以使用简单的算术定律得出结论:除以两个数字的 gcd 的数字也将除以这两个数字本身。因此,在 for 循环中从 i=1 迭代到 sqrt(gcd(x,y)) 将帮助我们获得该数字的所有公约数。

然后,检查每个 i 直到 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。这里我除以 gcd(18,27),即 16/2,等于 8。因此 gcd(x,y)/i 也会除 gcd(x,y) 得到 i。<=4,即 sqrt(16)。让我们考虑 i=2。这里我除以 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 的 gcd。

  • 初始化变量名称 ans = -1。

  • 在 for 循环中从 i=1 迭代到 i<=sqrt(gcd(x,y)) 并不断检查 i 是否整除 gcd(x,y)。<=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] 范围内两个数的 gcd 问题的方法。这就是我们如何在 C++ 中使用各种不同的函数来解决上述问题。

我希望您觉得这篇文章很有帮助,并澄清您与该问题有关的所有概念。

以上是找到给定范围内的最大公约数的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.如果您听不到任何人,如何修复音频
3 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

C标准模板库(STL)如何工作? C标准模板库(STL)如何工作? Mar 12, 2025 pm 04:50 PM

本文解释了C标准模板库(STL),重点关注其核心组件:容器,迭代器,算法和函子。 它详细介绍了这些如何交互以启用通用编程,提高代码效率和可读性t

如何有效地使用STL(排序,查找,转换等)的算法? 如何有效地使用STL(排序,查找,转换等)的算法? Mar 12, 2025 pm 04:52 PM

本文详细介绍了c中有效的STL算法用法。 它强调了数据结构选择(向量与列表),算法复杂性分析(例如,std :: sort vs. std vs. std :: partial_sort),迭代器用法和并行执行。 常见的陷阱

我如何在C中有效处理异常? 我如何在C中有效处理异常? Mar 12, 2025 pm 04:56 PM

本文详细介绍了C中的有效异常处理,涵盖了尝试,捕捉和投掷机制。 它强调了诸如RAII之类的最佳实践,避免了不必要的捕获块,并为强大的代码登录例外。 该文章还解决了Perf

在C中如何有效地使用RVALUE参考? 在C中如何有效地使用RVALUE参考? Mar 18, 2025 pm 03:29 PM

文章讨论了在C中有效使用RVALUE参考,以进行移动语义,完美的转发和资源管理,重点介绍最佳实践和性能改进。(159个字符)

如何在C 20中使用范围进行更有表现的数据操纵? 如何在C 20中使用范围进行更有表现的数据操纵? Mar 17, 2025 pm 12:58 PM

C 20范围通过表现力,合成性和效率增强数据操作。它们简化了复杂的转换并集成到现有代码库中,以提高性能和可维护性。

如何使用C中的移动语义来提高性能? 如何使用C中的移动语义来提高性能? Mar 18, 2025 pm 03:27 PM

本文讨论了使用C中的移动语义来通过避免不必要的复制来提高性能。它涵盖了使用std :: Move的实施移动构造函数和任务运算符,并确定了关键方案和陷阱以有效

动态调度如何在C中起作用,如何影响性能? 动态调度如何在C中起作用,如何影响性能? Mar 17, 2025 pm 01:08 PM

本文讨论了C中的动态调度,其性能成本和优化策略。它突出了动态调度会影响性能并将其与静态调度进行比较的场景,强调性能和之间的权衡

C语言数据结构:树和图的数据表示与操作 C语言数据结构:树和图的数据表示与操作 Apr 04, 2025 am 11:18 AM

C语言数据结构:树和图的数据表示与操作树是一个层次结构的数据结构由节点组成,每个节点包含一个数据元素和指向其子节点的指针二叉树是一种特殊类型的树,其中每个节点最多有两个子节点数据表示structTreeNode{intdata;structTreeNode*left;structTreeNode*right;};操作创建树遍历树(先序、中序、后序)搜索树插入节点删除节点图是一个集合的数据结构,其中的元素是顶点,它们通过边连接在一起边可以是带权或无权的数据表示邻

See all articles