1回答
用欧几里得算法计算两个数'x‘和'y’的GCD的最坏情况发生在'x‘和'y’是连续的fibonacci数时。假设'x‘和'y’是斐波那契数列的第(N)和(n-1)项。然后，对函数GCD(x，y)的调用还包括(n-3)个递归调用，每个操作在O(1)时间内运行。那么我们可以说这个算法的运行时间</em
浏览 0提问于2015-07-07得票数 1
1回答
unsigned int gcd(unsigned int n, unsigned int m)if (n == 0) if (m == 0) { n = n − m; m = m − n;return n;使用while循环的迭代GCD算法的一些伪代码。没有被2整除的地方，所以我不认为它是对数的。因为while循环运行<
浏览 6提问于2017-02-07得票数 0
我使用欧几里德算法的标准版本(即GCD(270,192) = GCD(192，)= ...repeat，直到0)来确定两个数字是否是相互关联的。我运行算法，检查GCD是否为1，并使用它来确定它们是否为1。
问题是，我正在为RSA做这件事，当我用5到6个数字测试算法时，需要花费大约4秒的时间，所以我需要一种方法来优化算法来处理数百位数字。我在网上找到了对扩展欧几里得算法</e
浏览 0提问于2018-01-04得票数 0
代码强制问题119A-#include<iostream>int a,b,i,n;{z=i; return z;int main() cin>>a>>b>>n; {
{
浏览 0提问于2013-12-14得票数 0
1回答
我编写了两个不同的实现来找到两个大数字的gcd。采用欧几里得算法的简单算法在速度上总是优于二进制算法。我的二进制算法实现不好吗？a = 5**100 - 1 if b == 0: return a
def <em
浏览 0提问于2020-04-30得票数 1
A和他的朋友从整数店各买了一个号码，A有N号，他的朋友有M. A想两个号码都是同质数。为了达到这个目的，A将两个数字除以可以将两个数字除以的最大数。A想知道这个运算后的数字之和，帮他找出那个和。++) divider=i;}
但是预期的运行时复杂度是但是我的代码给出了O(n)。
浏览 4提问于2022-01-20得票数 4
回答已采纳
4回答
对于一个数字y，我希望计算x1和x2的公共因子尽可能接近y。
我相信是时候重新表达我的问题了，更清楚。这不是关于整数..。那么，假设我们有两个数字x1和x2。我想要找到的是一个接近y的数字y，因此x1 % y'和x2 % y'非常小(例如，比0.02小，但让我们把这个数字称为LIMIT)。换句话说，我不需要一个最优的算法，而是一个很好的近似。我感谢大家的时间</em
浏览 11提问于2012-02-08得票数 10
回答已采纳
Steven在“编程挑战”一书中给出了以下代码中的gcd函数，以求整数x和y，从而使ax+by = gcd(a，b)。例如，如果a= 34398，b= 2132 ( gcd = 26)，下面的代码执行的算法应该返回34398×15 + 2132×−242 = 26。寻找x和y的算法基于基例y=1和x=0，因为a* 1+0*0 = gcd(a,0)，根据欧几里德算法，gcd(34398,2132)减少
浏览 8提问于2021-12-28得票数 -2
回答已采纳
1回答
void mpz_gcd (mpz_t rop, mpz_t op1, mpz_t op2);
目前，只有当N<3时，二进制算法才能用于GCD。对于大于GCD_DC_THR
浏览 3提问于2013-02-20得票数 3
回答已采纳
1回答
I发现二元GCD算法的时间复杂度很难计算，也被称为Stein算法，它被认为是O(n^2)，其中n是两个数中较大的位数。不是应该是O(n)吗?算法如下：
1.gcd( 0，v) = v，因为一切都是零，v是除以v的最大数，gcd( u，0) =U gcd(0，0)不是通常定义的，但是设置gcd(0，0) =0很方便。同样，如果u是奇数，v是偶数，则gcd</
浏览 1提问于2013-08-27得票数 1
回答已采纳
4回答
我正在研究一些需要大量使用GCD算法的东西，我希望它能尽可能快。我尝试过正常的方法，二进制方法，和回忆录的方法，我认为它会比它更好的工作。我从中复制了二进制方法，只做了一些小的调整。(0, y) == y; GCD(x, 0) == x, GCD(0, 0) == 0 */ return y; gcdY -= gcdX;
浏览 4提问于2015-01-10得票数 2
回答已采纳
1回答
我想知道是否有可能将它们转换成另一对整数，只使用下面提到的4个操作，每次任意次数。这些行动如下：or (x+y,y)or (x,x-y)
就像。
浏览 1提问于2015-06-25得票数 3
回答已采纳
我试图找到数字的lcm (1，2，3，4...20)，这是一个非常简单的java程序，但它给了我一个错误。这个错误只出现在我运行循环到20的时候，但不会出现在我运行到10的时候。static long gcd(long a, long b) if(a==b) return a;
{ } return <
浏览 15提问于2019-09-12得票数 0
回答已采纳
2回答
我只能找到关于如何递归地和迭代地实现gcd函数的文章，但是我找不到这个。我确信它在Stackoverflow上，但是我找不到它，所以如果它是一个重复的帖子，我很抱歉。我看过维基百科()的分析，无法理解它们之间的重复关系。
考虑在C中递归实现的GCD函数的以下实现，它有一个先决条件，即这两个数字必须是正的，不管这两个数字与运行时无关。int gcd( int const a, int const b
浏览 2提问于2013-08-08得票数 4
回答已采纳
我明白了生日的问题，算法会期望用\mathcal{O}(\sqrt{N})的时间来寻找一个循环。然而，其中一个步骤涉及到计算\gcd(\mid x-y \mid, N)，我猜想它使用了欧几里德算法，即\mathcal{O}(\log(N))。那么，它不应该在\mathcal{O}(\sqrt(N) * \log(N))中运行吗？
https://en.wikipedia.org/wiki/Pollard%27s_rho_算
浏览 0提问于2022-06-10得票数 2
1回答
我是一名计算机科学专业的学生，我正在独立学习算法课程。我的解决方案：两个素数p和q和，N= pq对于任何e相对素数(p−1)(q−1)
这是我写的算法，但我很难做到。q' = gcd_steps.t
浏览 2提问于2022-03-17得票数 1
回答已采纳
2回答
我试图在C++/C中建立一个有效的算法，以求丢番图方程Ax+By+Cz=D的一个(任意)解和解的数量，其中A,B,C,D是用户给出的整数，x,y,z运行在用户给定的范围内。x,y,z也是整数。因此，算法中的第一件事是找出是否有解决方案：最后，如果gcd</
浏览 4提问于2014-11-21得票数 2
回答已采纳
这段代码本应简化小数，并将小数转换为小数，但当我放入除法较大的小数(数字大于7或8位)时，它会有很大的滞后。i === 0 ) return i; };
我试图让它像Wolfram Alpha一样工作，因为你可以放入带有大除法的分数，并且当你显示它的快速渲染结果时，它不会冻结一点。有没有人可以修复这段代码以处理更大的数字。我想你得用不同于我的算法。另一方面，有没有人知道WA的</e
浏览 0提问于2012-08-01得票数 1
回答已采纳
我目前使用此代码来查找gcd和lcm。 while b != 0: return a
result = a*b/gcd(a,b)但是
浏览 0提问于2012-01-11得票数 1
回答已采纳
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号