2

我今天在开发人员工作面试中遇到了以下情况，这是问题之一，只有一个我没有回答。

连接数 NN 次，然后计算他的模数到 2017 年。

例如：对于 N=5，数字将为 55555，结果将为 Mod(55555,2017) = 1096 对于 N=10，数字将为 10101010101010101010，结果 Mod(10101010101010101010,2017) = 1197

现在我必须计算的数字是 58184241583791680。我得到的唯一提示是 58184241583791680 连接 58184241583791680 乘以模数 2017 的结果是一个 4 位数字。

我在 math.stackexchange 上发布了这个问题，我得到了解决这个问题的数学方法，而不是蛮力。

我用JAVA编写了以下代码

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;

public class Puzzle {
    final static BigInteger M = new BigInteger("2017");

public static void main(String [ ] args) {
    for (long n : new long[] { 1L, 2L, 5L, 10L, 20L }) { 
        System.out.println(n + " --> " + bruteForce(n) + " --- " + formulaV2(n));
    }
}


private static BigInteger bruteForce(long n) {
    String s = "";
    for (long i = 0; i < n; i++) {
        s = s + n;
    }
    return new BigInteger(s.toString()).mod(M);
}

private static BigInteger formulaV2(long n) {
    String aux = String.valueOf(n);
    long L = aux.length();
    long K = n;           

    double op1 = Math.pow(10,L*K);
    BigDecimal minus1 = new BigDecimal(1);
    BigDecimal p1 = new BigDecimal(op1).subtract(minus1);

    double op2 = Math.pow(10,L);
    BigDecimal p2 = new BigDecimal(op2).subtract(minus1).pow(-1,MathContext.DECIMAL64);

    BigDecimal R = new BigDecimal(n).multiply(p1).multiply(p2);
    R = R.setScale(0,BigDecimal.ROUND_UP);
    BigInteger ret = R.toBigInteger();
    return ret.mod(M);
}
}

我正在使用 BigInteger 和 BigDecimal，因为我想获得非常大的数字（16 位以上）的值。

bruteForce 方法将简单地连接循环内的数字，而 formulaV2 方法将使用数学论坛中提出的问题中的公式。

bruteForce 方法仅用于验证。

然而，公式方法适用于 N<10，但不适用于 N>=10。在 N=10 我得到不正确的结果。

编码似乎与提供的公式一致（至少对我来说，也许我缺少一些东西），并且公式是正确的（我在 Wolfram Alpha 中检查过）。

我的猜测是我有精度问题，也许 BigDecimal 在这种情况下不是正确的对象？

4

5 回答 5

4

使用数学！一个好的面试官希望你用你的大脑解决问题，而不是用蹩脚的代码蛮力解决问题。

在这种情况下，他可能希望你使用等式

  1. ab mod n = [(a mod n)(b mod n)] mod n

  2. (a + b) mod n = [(a mod n) + (b mod n)] mod n

并且例如将四位数字连接三次的事实与 相同，xyzu * 100010001后者可以进一步分解为10000^0+10000^1+10000^2。

现在在你的情况下，基数 x 和重复次数 y 是相同的，而且都相当大。但是模数 n 很小。令 D 为大于 x 的 10 的下一个幂。

因此，D mod n 实际上不是 D，而是小于 2017。而不是计算 D^y，您实际上可以计算 ((D mod n)^y) mod n，如果您在 for 循环中执行此操作，它将最终（在最多 2017 步之后）循环或变为 0。因此，您最多可以在 2017 次迭代中计算该项。因此，这种智能方法的复杂性是 O(n)，其中 n 是模项，而简单的方法将需要 O(x*y) 内存。

有了这些技巧，你应该可以在没有BigInteger 的情况下做到这一点，而且速度要快得多。

于 2016-08-21T21:16:22.030 回答
3

这是个问题：

double op1 = Math.pow(10,L*K);

例如，当n = 20、L*K = 40和op1 = 10000000000000000303786028427003666890752。至于为什么，通常的浮点业务：它是最接近的。没有double值恰好为 1E40。

op1不会那样打印（你会看到 1E40 并认为一切都很好），但它会像那样转换。然后你将使用BigDecimalwhich 很好（虽然很奇怪），但在那之前它已经出错了。

我假设您使用过，BigDecimal 因为您是从 a 转换而来的double，否则您会使用BigInteger. 只需使用BigInteger.pow而不是Math.pow它可能会起作用（它解决了这个问题，如果还有什么我没有注意到但我不能保证它会起作用）。

Math.pow(10,L)另一方面不应该是一个问题，因为L现在已经足够低了。你也可以改变它，让它在大L范围内工作。

于 2016-08-21T20:09:11.427 回答
3

double op1 = Math.pow(10,L*K)

对于较大的 n 值，这里将溢出。Double.MAX_VALUE ~ 1.7*10^308 (ie) 对于 L*K > 308，它将溢出。

编辑：正如 harold 在他的回答中提到的那样，double 将无法准确地表示更小的值。

于 2016-08-21T20:09:42.090 回答
2

我在https://stackoverflow.com/questions/38988665/java-puzzle-whats-the-correct-answer#comment65349106_38988665的评论中阐述了这一切，但你可以接受@Anony-Mousse 和上面其他人所说的和工作用它。

一个关键是预先找到 10^17 mod 2017。Wolfram Alpha 是正确的，无论如何是 599，但在其他平台上，您可能需要将其视为 ((10^9 mod 2017) (10^8 mod 2017))mod 2017 以获得 599。您还需要 58184241583791680 mod 2017 是 2005 年（Wolfram 再次做到了这一点，但如果你不将它分解成类似的东西，较小的平台可能会动摇（（（581842415 mod 2017）（10^8 mod 2017）mod 2017）+83791680）mod 2017。

因此，在（58184241583791680 但不用担心）过程的每个步骤中，您都将当前数字乘以 10^17（将其移至为串联腾出空间）并添加 58184241583791680。但我们可以在 2017 年完成这一切. 在序列语言中，a sub 1 = 2005 and a sub (n+1)=((a sub n)*599+2005) mod 2017。这是 for 循环中的关键步骤。我在 R 中完成了前 4040 个左右的术语（很高兴你可以将它们交互地放在屏幕上并仔细研究它们——这门语言在我身上成长了），尽管它真的足以做到一半（古老的鸽洞原理在起作用）。直到你真正走到 2017 年，也就是 2005 年，它们才会循环。子 4033 也是如此。

一般来说，a sub n = a sub (n mod 2016)。您想要一个子 58184241583791680。58184241583791680 mod 2016 是 224 说 Wolfram Alpha [再次在较小的平台上，您可能需要将其分解为 (((581842415 mod 2016)*(10^8 mod 2016) mod 2016)+83791680)mod 2016]，所以你想要一个子 224。

如果人们想检查自己或我，我在 R 上得到了 465。但正如上面所指出的，这个过程才是问题真正感兴趣的地方。

于 2016-08-22T09:15:49.393 回答
-1 
import java.math.BigInteger;
class Puzzle {

    final static BigInteger M = new BigInteger("2017");
    private static BigInteger compute(long n) {
         String s = "";
         String a = new BigInteger(n+"").mod(M)+"";

         for (long i = 0; i < Integer.parseInt(a); i++) {
              s = s + a ;
              s = new BigInteger(s).mod(M)+"";
         }
         return new BigInteger(s.toString()).mod(M);

    }

    public static void main(String args[]) {

       for (long n : new long[] { 1L, 2L, 5L, 10L, 20L, 58184241583791680L }) {
           System.out.println("" + n + ": " + compute(n));
       }

    }
}
于 2019-11-16T14:07:29.313 回答