java 一个N数连接N次的模

mgdq6dx1  于 2023-05-21  发布在  Java
关注(0)|答案(6)|浏览(128)

我今天在一个开发人员工作的面试中遇到了以下情况,这是其中一个问题,也是我唯一没有回答的问题。
把这个数连起来N N次,然后计算出他在2017年之前的模数。
例如:对于N=5,数字将为55555,结果将为Mod(55555,2017)= 1096;对于N=10,数字将为101010101010101010,结果Mod(101010101010101010,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方法将简单地在循环中连接数字,而formulaV 2方法将使用数学论坛中提出的问题中的公式。
bruteForce方法只是用于验证。
然而,公式方法在N =10时工作良好<10 but no for N>。在N=10时,我得到了不正确的结果。
代码似乎与提供的公式一致(至少对我来说,也许我遗漏了一些东西),公式是正确的(我在Wolfram Alpha中检查过)。
我的猜测是,我有精度问题,也许BigDecimal在这种情况下不是合适的对象?.

jucafojl

jucafojl1#

**使用数学!**一个好的面试官希望你用你的大脑和解决问题,而不是用蹩脚的代码来解决问题。

在这种情况下,他可能想让你用等式

  1. ab mod n = [(a mod n)(b mod n)] mod n
    1.(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步后)cycle 或变为0。因此,您最多可以在2017次迭代中计算此项。所以这种聪明的方法的复杂度是O(n),其中n是模项,而朴素的方法需要O(x*y)内存。
    有了这些技巧,你应该能够在不使用BigInteger的情况下完成这个任务,而且速度要快得多。
bbuxkriu

bbuxkriu2#

这是一个问题:

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

例如,当n = 20L*K = 40op1 = 10000000000000000303786028427003666890752时。至于为什么,通常的浮点业务:这是最接近的了不存在值正好为1E40的double
op1不会像这样打印(你会看到1E40,并认为一切都很好),但它会像这样转换。然后你将使用BigDecimal,这很好(虽然有点奇怪),在此之前它已经出错了。
我假设您使用了BigDecimal *,因为 * 您是从double转换而来的,否则您将使用BigInteger。只要使用BigInteger.pow而不是Math.pow,它可能会工作(它修复了这个问题,如果还有什么我没有注意到的,但我不能保证它会工作)。
另一方面,Math.pow(10,L)不应该是一个问题,因为L足够低。现在。你也可以改变它,让它在大的L上工作。

uelo1irk

uelo1irk3#

double op1 = Math.pow(10,L*K)
这里对于n的大值将溢出。Double.MAX_VALUE 〜 1.710^308(即),对于LK > 308,它将溢出。
编辑:double将无法准确表示harold在回答中提到的小得多的值。

ct2axkht

ct2axkht4#

我在https://stackoverflow.com/questions/38988665/java-puzzle-whats-the-correct-answer#comment 65349106_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和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。但正如上面所指出的,过程才是问题真正感兴趣的。

llmtgqce

llmtgqce5#

实际上,你可以在**log(n)**时间内完成。这比上面解释的任何方法都快。
你的工具箱里需要的东西:
1.power(a,B)with some modulo(如果模是素数,在你的情况下,它总是正确的)
1.在
a%x + B%x ==(a+b)%x中乘法相似的知识。

1.求模逆

如果你不知道这些方法,你可以谷歌它。

现在到解决方案:
首先让你给定的num是1234,然后我们需要计算1234 1234 1234... 1234次
它等于1234 + 10^4 * 1234 + 10^8 * 1234 + 10^12 * 1234... 10^(4* 1233)* 1234

我们得到GP

==1234(10^(41234)- 1)/(10^4 - 1)**
用x替换1234,用y替换4(N中的位数)
我们得到x*(10^(x*y)-1)/(10 ^y- 1)
该幂函数和反函数仅花费log(n)时间
现在我们的答案是x (power(10,xy)-1)* inverse(power(10,y)-1);对所有这些取模就能得到答案
我可能犯了一些错误,请原谅。这可能是一个heafty读如果你不知道上述要求.

t40tm48m

t40tm48m6#

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

    }
}

相关问题