N 数串接 N 次的模数

Question

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

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

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

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

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

我在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

这是一个问题：

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

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

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

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

另一方面，

Math.pow(10,L) 应该不是问题，因为 L 现在已经足够低了。不过，您也可以更改它，让它适用于大型 L。

Answer 2

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

此处的 n 值较大时会溢出。 Double.MAX_VALUE ~ 1.7*10^308 (即) 对于 L*K > 308，它会溢出。

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

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是一样的，而且都比较大。但是 modulus n 很小。令 D 为大于 x 的下一个 10 次方。

因此 D mod n 实际上不是 D，而是小于 2017。而不是计算 D^y，您实际上可以计算 ((D mod n)^y) mod n，如果你在 for 循环中这样做，它最终（最多 2017 步之后）cycle 或变为 0。因此你最多可以在 2017 年计算这个术语迭代。因此，这种智能方法的复杂度为 O(n)，其中 n 是 modulo 项，而朴素的方法将需要 O(x*y) 内存。

有了这些技巧，您应该可以不使用 BigInteger，并且快很多。

Answer 4

我在的评论中列出了所有内容，但您可以采纳@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。但我们可以全部完成 mod 2017。在序列语言中，a sub 1 = 2005 和 a sub (n+1)=((a sub n)*599+2005) mod 2017。这是 for 循环中的关键步骤。我在 R 中完成了前 4040 个左右的术语（很喜欢你可以将它们交互式地放在屏幕上并仔细研究它们——我对这种语言越来越感兴趣），尽管它真的足以完成大约一半（好的老鸽笼原则在起作用）。他们不会循环，直到你真的一路走到 2017 年，也就是 2005 年。 sub 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], 所以你想要一个sub 224.

如果人们想检查自己或我，我上了 R 那是 465。但是正如上面指出的，过程才是问题真正感兴趣的。

Answer 5

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));
       }

    }
}

N 数串接 N 次的模数

Modulus of a N number concatenaded N times

java

algorithm

math

precision

mod