java - N 数串接 N 次的模数

Question

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

将N个数串联N次，然后计算出他到2017年的模数。

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

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

我发布了 this question在 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 在这种情况下不是合适的对象？

Answer 1

使用数学!一个好的面试官希望您使用您的大脑并解决问题，而不是用糟糕的代码蛮力解决问题。

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

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 mod n)^y) mod n 而不是计算 D^y，如果您在 for 中执行此操作循环它最终将(最多 2017 步之后)循环 或变为 0。因此，您最多可以在 2017 次迭代中计算该术语。因此，这种智能方法的复杂度为 O(n)，其中 n 是模项，而朴素方法将需要 O(x*y) 内存。

有了这些技巧，您应该能够在不 BigInteger 的情况下执行此操作，而且速度更快。