问题标签 [lcm]

我正在尝试解决在线法官问题： http: //opc.iarcs.org.in/index.php/problems/LEAFEAT

简而言之，问题是：

如果给定一个整数 L 和一组 N 个整数 s1,s2,s3..sN，我们必须找出从 0 到 L-1 有多少个数不能被任何 'si' 整除。

例如，如果给定我们， L = 20那么S = {3,2,5}从 0 到 19 有 6 个数字不能被 3,2 或 5 整除。

L <= 1000000000 和 N <= 20。

我使用了包含-排除原则来解决这个问题：

这是我解决这个问题的代码

next_subset(n)生成数组中大小为 n 的下一个子集，A如果没有子集，则返回 0，否则返回 1。它基于此stackoverflow 问题中接受的答案所描述的算法。

该lcm(a,b)函数返回 a 和 b 的 lcm。该get_lcm(n)函数返回 中所有元素的 lcm A。它使用属性：LCM(a,b,c) = LCM(LCM(a,b),c)

当我将问题提交给法官时，它会给我一个“超出时间限制”。如果我们使用蛮力解决这个问题，我们只能得到 50% 的分数。

由于最多可以有 2^20 个子集，我的算法可能会很慢，因此我需要一个更好的算法来解决这个问题。

编辑：

在编辑我的代码并将函数更改为欧几里得算法后，我得到了错误的答案，但我的代码在时间限制内运行。它给了我对示例测试的正确答案，但对任何其他测试用例都没有；这是我运行代码的ideone的链接，第一个输出是正确的，但第二个不是。

我解决这个问题的方法正确吗？如果是，那么我在代码中犯了一个错误，我会找到它；否则谁能解释什么是错的？

我们如何编写代码来找到以下解决方案： (N+1)*X =LCM( 1,2,3,4,5,6,......,N,N+1) 使用 mod 当它变得大于 (10^9 +7) 。使用 MOD=(10^9 +7)。我写了以下代码片段，但它不起作用：

你好考虑二进制数组：

我想将此数组的所有奇数行的 lcm 提高到 2x，其中 x = 3。这意味着我需要为第 1、第 3 和第 5 行获取 lcm。

但我需要一个可以应用于 ny x 和 A 的通用代码，因为两者可能不同。（无论 A 和 xi 给出什么，都应该获得 A 的奇数行高达 2x 的 lcm。

我在 LCM 上解决了以下问题：Calculate LCM of N numbers modulo 1000000007

我的方法：

当我提交我的解决方案时，我得到了错误的答案。约束是：

在 IDEONE

我想我因为溢出而得到错误的答案。如何改进我的代码？

谢谢！

我有一个整数数组，我试图找到数组中所有值的 LCM（最小公倍数）。我已经lcm单独写了一个方法；它需要两个值作为输入，并返回 lcm。我的lcm方法工作得很好，但是当我用它来查找所有值的 LCM 时，我得到了错误的答案。

这是我的gcd和lcm方法：

这就是我对数组值的 lcm 所拥有的：

当我放入一个包含数字 1 到 5 as arr、0 asstart和数组长度 as 的数组时end，我得到 30 作为答案，而我想要 60。当我放入一个包含从 1 到所有数字的数组时10，我得到840而不是2520。我真的无法解释。

算法应该可以工作——我已经在脑海中解决了。无法弄清楚我的代码有什么问题。

任何帮助将不胜感激。

我需要找到一系列数字的最小公约数（最多 100 000 个数字，每个数字都在 [0, 2 000 000 000] 的范围内）

我正在使用以下算法 lcm(a,b) = (a/gcd(a,b)) * b

为超过 2 个数字查找 lcm 的标准方法 lcm(a, lcm(b,c))... 适用于较小的输入值。

但是，对于大输入，即使我使用 long long int，它也会开始出现溢出错误...

如何避免许多较大整数值出现溢出错误？

感谢您的帮助

这是我的代码：

我究竟做错了什么？我不断收到错误，因为显然y = gcd(a,b)是 aNoneType并且它必须是整数。但据我所知，它是一个整数。

我一直在尝试更深入地编程，所以我一直在尝试制作一个简单的程序，它以两个数字作为输入，并计算最小公倍数。我在 Python 中这样做是因为我不知道如何在 Java 中接受输入。现在发生的事情是程序在我输入数字后挂起，什么也没有发生。这里的任何指针将不胜感激。谢谢你。

所以这个程序所做的是使用 Scanner 类将两个数字作为输入，并计算这两个数字的最小公倍数。一切似乎都在工作，除了 lcm 方法不会返回任何东西。我的“break”语句可能搞砸了，但我不知道有任何其他方法可以摆脱嵌套在 while 循环中的 if 语句。还有一个问题：使用 while(True) 循环是好做法还是坏做法？因为我看到了很多关于它的不同意见。如果有人对 while(True) 循环有更好的选择，我会很高兴听到它们。谢谢！

我必须找到所有数字 1 到 20 的 lcm，然后我想出了这个代码。它虽然效率低下，但也给出了比正确答案多 2 的答案。谁能告诉我为什么？