一个长数字的前N位如何实现常数时间复杂度？

Question

在一个Project Euler问题中，我需要处理可能有数百位数字的数字。而且我需要对前9个数字进行一些计算。

我的问题是：确定100位整数的前N位的最快方法是什么？用模/余数求得最后N位很容易。对于前几位，我可以应用模运算100次以逐位获取，或者我可以将数字转换为字符串并截断，但它们都是线性时间。是否有更好的方法？

- Konrad Garus

---

大多数项目欧拉解决方案都有“啊哈！”解决方案以及“蛮力”解决方案...另外，您的问题与编程无关。 - Mitch Wheat

为什么将数字转换为字符串并执行str[i]是线性的？ - user418748

@Mitch：这个问题到底怎么会“与编程无关”呢？ - bendin

有一个非常好的问题来自一个大约有10k经验值的人。你能提供更多的细节吗？整数是如何表示的，以及你想如何使用这9个数字？顺便说一句，如果你需要这个，那么看起来你的当前解决方案是错误的。 - max taldykin

Answer 1

您可以使用以下函数来计算数字的数量：

(defn dec-digit-count [n]
  (inc (if (zero? n) 0
  (long (Math/floor (Math/log10 n))))))

现在我们知道有多少位数字，我们想只留下前9位。我们需要做的是用10^(digits-9)来除以这个数字，或者在Clojure中：

(defn first-digits [number digits]
  (unchecked-divide number (int (Math/pow 10 digits))))

并且可以这样调用：(first-digits your-number 9)，我认为它的时间复杂度是稳定的。我只是不确定log10实现是否正确。但是，它肯定比取模/循环解决方案快得多。

另外，还有一种更简单的解决方案。你可以直接复制粘贴数字的前9位。

- Goran Jovic

---

谢谢，由于某种原因我没有想到log10。一旦你找到它，就显得非常明显了。 :-) - Konrad Garus

@Konrad：引用 Mitch Wheat 的话来说：“A-ha！” :) - Goran Jovic

Answer 2

也许你可以使用一个由两个数字组成的元组，而不是一个长数字：[前几位数字，后几位数字]。对它们进行操作时，每次都将第一个数字从右侧截断到所需长度（两倍于条件 - 在你的情况下是9），并将第二个数字从左侧截断到相应长度。 就像这样：

222000333 * 666000555
147|852344988184|815

222111333 * 666111555
147|950925407752|815

因此，您只需要进行两个小计算：222 * 666 = 147[852] 和 333 * 555 = [184]815。

但是，“a ha”解决方案的评论对于欧拉项目来说是最相关的 :)

- zmila

---

谢谢，事实证明这是解决那个问题最受欢迎和最简单的方法。 - Konrad Garus

Answer 3

在Java中：

public class Main {
    public static void main(String[] args) throws IOException {
        long N = 7812938291232L;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
        N = 1234567890;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
        N = 1000000000;
        System.out.println(N / (int) (Math.pow(10, Math.floor(Math.log10(N)) - 8)));
    }
}

产生

781293829
123456789
100000000

- Victor Sorokin

Answer 4

这可能会对您有所帮助 幂运算的前n位数字

以及来自这个问题的答案

该算法的复杂度为O(b)。但很容易将其更改为O(log b)

- user467871