N个数的模级联N次

Question

我今天在开发人员工作面试中遇到了以下场景，这是其中一个问题，也是我唯一没有回答的问题。

将数字串联N次，然后在2017年前计算他的模数。

例如：对于N=5，数字为55555，结果为Mod（55555 2017）=1096；对于N=10，数字为10101010101010，结果Mod（101010101010102017）=1197

现在我要计算的数字是58184241583791680。我得到的唯一提示是58184241583791680串联58184241583791680乘以模数2017的结果是一个4位数。

我把这个问题贴在了数学上。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很有效

编码似乎与提供的公式一致（至少对我来说，可能有什么我遗漏了），并且公式是正确的（我在Wolfram Alpha中进行了检查）。

我的猜测是我有精度问题，也许BigDecimal不是这种情况下合适的对象？。

Answer 1

double op1=Math。功率（10，L*K）

对于n.Double的大值，这将溢出。L*K的最大值约为1.7*10^308（即）

编辑：正如哈罗德在回答中提到的那样，double不能准确地表示更小的值。

Answer 2

这是一个问题：

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

例如，当n=20、L*K=40和op1 = 10000000000000000303786028427003666890752时。至于原因，通常的浮点业务：这是它能得到的最接近的。没有值正好为1E40的双精度。

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

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

Math.pow（10， L）另一方面应该不是问题，因为L现在已经足够低了。不过，您不妨也更改一下，让它适用于大型L。

Answer 3

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

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

>

ab mod n=[（a mod n）（b mod n）]mod n

（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的情况下完成这项工作，而且速度要快得多。