o(1) 中的最大公因数？
Greatest Common Factor in o(1)?
注意：这不是问如何在 O(n) 中解决 GCF
您有两个整数，n 和 i。我们如何（在伪代码中）在恒定时间内计算 GCM(n, i)，其中 n 和 i 的域为 0 -> infinity？
我见过的唯一解决方案是使用递归或循环。如果可能的话，我想在固定时间内完成。
谢谢。
好吧，从技术上讲这是可能的，是的——例如，通过创建一个预先计算的结果矩阵。但由于疯狂的内存消耗，这几乎不实用。
N.B.:这个方法有一个重要的前提：
n, i ∉ [0; ∞)，而是 n, i ∈ [0; M], M ∈ [0; ∞) — 即值范围任意大，但仍然固定。
否则，将 n 和 i 读入内存的操作将是渐近线性的，使得 O(1) 甚至在理论上是不可能的。
注意：这不是问如何在 O(n) 中解决 GCF
您有两个整数，n 和 i。我们如何（在伪代码中）在恒定时间内计算 GCM(n, i)，其中 n 和 i 的域为 0 -> infinity？
我见过的唯一解决方案是使用递归或循环。如果可能的话，我想在固定时间内完成。
谢谢。
好吧，从技术上讲这是可能的，是的——例如，通过创建一个预先计算的结果矩阵。但由于疯狂的内存消耗，这几乎不实用。
N.B.:这个方法有一个重要的前提：
n, i ∉ [0; ∞)，而是 n, i ∈ [0; M], M ∈ [0; ∞) — 即值范围任意大，但仍然固定。
否则，将 n 和 i 读入内存的操作将是渐近线性的，使得 O(1) 甚至在理论上是不可能的。