问题标签 [diophantine]

我正在尝试编写一个算法来确定一个线性方程，特别是 ax + by = c 的形式，对于给定的 a，b，c 是否具有正整数解。它需要高效，因为数字 a、b 和 c 可以在 0<=a,b,c<=10^16 的范围内。我将如何解决这个问题？

由于这是一个有问题的丢番图方程，我试图检查 a 和 b 的 GCD 是否除以 c，但这样我无法区分正解、负解或零解。

确定线性丢番图方程非负值解存在性的算法

我在这里找到了解决方案，但我不太明白。也许有人可以为我简化它？因为这个很一般，我只对有 2 个变量的方程感兴趣。

我正在尝试求解方程

其中 all 的值xi被限制为[0, 0.1, 0.2, ..., 0.9, 1]。

目前，我正在通过首先生成一个 n 维数组来解决这个问题mat，其中每个元素位置的值是轴值的总和，其变化范围为axisValues = 0:0.1:1：

然后我搜索结果数组中等于一的所有条目。代码（如下所示以进一步说明）运行良好，并且已针对多达 5 个维度进行了测试。问题是，运行时间呈指数增长，我需要脚本在多个维度上工作。

我觉得以下使用问题对称性的想法可能有助于显着减少计算时间：

对于二维矩阵，所有满足上述条件的条目都位于从mat(1,11)到的对角线上mat(11,1)，即从 的最大值x1到 的最大值x2。

对于 3D 矩阵，所有条目都满足位于通过mat(1,1,11)、mat(1,11,1)、的对角线平面上的条件mat(11,1,1)，即从 的最大值x1到x2的最大值x3。

对于更高维也是如此：所有感兴趣的矩阵元素都位于一个n-1维超平面上，该维超平面固定在每个维中的最高轴值上。

问题是：有没有办法直接确定这些n-1维度超平面上元素的索引？如果是这样，整个问题可以一步解决，而无需计算 n 维矩阵的所有条目，然后搜索感兴趣的条目。

您正在求解一个简单的丢番图方程，并使用以下 Python 代码来完成。

在保留代码的基本特征的同时，您将如何“很好地”表示它，以便它扩展以在丢番图方程中提供更多变量？

有九种解决方案：

1 6 1

1 5 2

1 4 3

1 3 4

1 2 5

1 1 6

2 3 1

2 2 2

2 1 3

我正在尝试用 Python 编写算法来求解线性丢番图方程。

我认为我的算法是正确的，因为我已经在论文上对其进行了测试，但是当我运行它时，它会返回奇怪的值。

我的代码：

它使用 7 个变量和 3 个辅助变量。用笔和纸对其进行测试后，使用以下值：

我明白了

但是，当我运行它时：

它返回：

我正在寻找整数分解的特定情况的有效解决方案。高效我的意思是比我目前拥有的要快得多O(2^n)（n 表示我们完成后数组中的元素数）。

假设我们有以下数组：[4, 5, 11]并且“目标”为 84。

我们想知道是否可以满足4*a + 5*b + 11*c = 84，

给定以下约束：

• 0 <= 一 <= 3
• 0 <= b <= 2
• 0 <= c <= 1

如果我们没有找到解决方案，我们将一个整数添加到数组中，比如 15：[4, 5, 11, 15]

现在我们想知道是否有任何满足4*a + 5*b + 11*c + 15*d = 84

鉴于

• 0 <= 一 <= 4
• 0 <= b <= 3
• 0 <= c <= 2
• 0 <= d <= 1

...然后我们重复这个过程，直到找到解决方案，或者最多 n 次。我想知道我们是否可以利用问题的重复性来找到有效的解决方案：

• “目标”不变
• 整数按升序排列
• 每次我们添加一个新元素时，a,b,c... 的最大约束增加 1
• 每次重复都会将某些内容添加到公式中，但没有任何更改（约束除外）

有任何想法吗？

在这篇文章中，我找到了一种确定 RGB 颜色亮度的算法：

亮度（某些色彩空间的标准）：（0.2126*R + 0.7152*G + 0.0722*B）

我想使用这个等式，从 开始rgb(0,0,0)，按照从最低到最高亮度的顺序生成所有 RGB 颜色，然后将它们绘制到 4096x4096 画布上。

我的问题是，对于 1670 万种不同的组合，我无法全部生成它们然后对它们进行排序，而不会导致浏览器崩溃或花费数天时间来完成渲染。所以我想找到一种方法来找到每个数字的倍数，这些数字将相加到下一个最小的数字。

例如，从 和 的 rgb 开始0,0,0，亮度将为 0 ( 0.2126*0 + 0.7152*0 + 0.0722*0 = 0)，下一个最小的发光 rgb 值将是0,0,1因为0.2126*0 + 0.7152*0 + 0.0722*1 = .0722，并且没有一组倍数可以相加为更小的数字。

前 19 个连续的亮度值如下（我可能错过了一两个，因为我手动计算了它们，但希望它有助于说明这一点）：

我似乎找不到任何模式，所以我希望那里可能有一个方程式或编码技巧，可以让我找到三个数字的倍数的最小总和，高于前一个总和，而无需蛮力强制它并检查每个可能的值。

编辑：我做了一些额外的研究，看起来解决方案可能在于使用线性丢番图方程。如果我取每个小数并乘以 1000，得到2126, 7152, & 722. 然后 1 乘 1 计数到2,550,000( 2126*255 + 7152*255 + 722*255)，我可以检查每个数字是否是方程的解2126r + 7152g + 722b = n，其中 n 是当前计数的数字，而 r、g 和 b 是未知数。如果我能做到这一点，我可以计算出下一个连续亮度值处所有可能的 rgb 值，甚至不必将重复亮度值的任何值加倍，我只需要进行 255 万次计算而不是 16.77+ 百万次（每种颜色一个）。如果有人知道如何编写这个方程，或者如果有人有更好的解决方案，我将非常感激。谢谢！

I would like to solve a first degree equation with multiple variables (not a system of equations) like :

10x + 5y + 7z = 630

Is there any way to solve it without using bruteforce?

Solutions must be integers.

为愚蠢的问题标题道歉。我在 Java 中遇到了一个非分级挑战，主要是确定是否存在两个正整数 x 和 y，使得 ax+by=c，其中提供了 a、b 和 c。

上下文是给你两个价值 a 和 b 的硬币，你必须确定它们是否可以以某种方式组合成等于 c 的数量。关键是你的代码不能包含任何类型的循环或递归函数。

到目前为止，我已经确定欧几里得算法似乎对这类问题有用；因为找到 a 和 b 的最大公约数可以证明 x 和 y 作为整数的存在，从而完成了方程。问题是 x 和 y 仍然可能是负数，就像集合 [3,7,11] 的情况。3 和 7 之间的最大公约数是 1，它们可以组合成 11 到 3(-1)+7(2)。

由于您显然不能使用负数量的硬币，因此 11 不会是“鸡块数”（参考麦乐鸡问题，我认为这是相关的）。所以我正在寻找的是一种完全不同的方法来尝试这个没有任何类型的循环，或者是关于如何实际确定 x 和 y 的值以查看是否为负数的建议。

我不一定要为此寻找代码，只是任何建议或指南都会有所帮助。如果您没有解决方案但有兴趣思考这个问题，推荐阅读扩展欧几里得算法、Bézout 恒等式、丢番图方程和Chicken McNugget 定理。

我正在使用 Python，但我不介意更改语言。我从我的研究中得到的只是计算一个区域内（晶格）点数量的工具，给出了包围它的平面的方程。其他工具用于优化多面体内部的给定函数（线性规划）。

单独找到格点怎么样？例如，一个函数

另外，我正在寻找可以在多变量场景中工作的东西（x、y、z、...的约束）。

我目前正在尝试使用ppl解决这个问题。

我正在尝试为 RSA 实现的 Scheme 中的扩展欧几里得算法编写代码。

我的问题是我无法编写递归算法，其中内部步骤的输出必须是连续外部步骤的输入。我希望它给出最外层步骤的结果，但可以看出，它给出了最内层步骤的结果。我为此编写了一个程序（它有点乱，但我找不到时间编辑。）：

各种帮助和建议将不胜感激。（PS我添加了给我们的说明的截图，但我看不到图像。如果有问题，请告诉我。）