如何在java中生成n个？

Question

我坚持使用一种算法,我需要生成n个数字'1',其中n<=10^16和n>=1.我成功地在一个for loopwith中生成了n个,BigInteger因为long它们也string没有成功.但问题是这个时间限制4 sec并且需要更多4 sec时间n>10^5.这显然是产生于O(n).我认为没有必要使用相应的代码.我发现很多网站但找不到任何解决方案.任何更好的算法都会有所帮助.谢谢.
编辑:这是一个谜题,其中n与m输入,我需要打印111...(n times) mod m,其中限制是1?N?10^16和2?M?10^9.例如,
假设n=3&m=3然后打印111%3其等于0
假设n=5&m=18然后打印11111%18其等于5.
如果您使用long或String然后NumberFormatException抛出然后我将其更改为BigInteger然后异常消失.

public static void main(String[] ar){
    Scanner in= new Scanner(System.in);
    int t=in.nextInt();
    while(t-->0){
        BigInteger n=new BigInteger(Long.toString(in.nextLong()));
        BigInteger m=new BigInteger(Long.toString(in.nextLong()));
        BigInteger s=new BigInteger("1");
        for(long i=1;i<n.intValue();i++)
            s = s.multiply(new BigInteger("10")).add(new BigInteger("1"));
        System.out.println(s.mod(m));
}

Answer 1

如果S(n)是n个,则这些方程式成立:

S(1) = 1
S(2n) = S(n) * (10^n + 1)
S(n+1) = S(n) * 10 + 1

您可以使用这两个重复(模m)来计算S(n)模m.

S(n) % m =
   1                                          [if n is 1]
   ((S(n/2) % m) * ((10^{n/2} % m) + 1)) % m  [if n is even]
   ((S(n-1) % m)) * 10 + 1) % m               [if n is odd]

你仍然需要能够有效地计算10 ^ n%m,虽然这可以通过使用求幂进行平方来完成,但也可以使用10 ^ n = 9*S(n)+1的事实.

使用10 ^ n和S(n)之间的后一种关系,可以得到这组方程式,这些方程式很容易编码为递归(或迭代)程序:

S(n) % m =
   1                                 [if n is 1]
   x*(9x+2) % m where x = S(n/2)%m   [if n is even]
   ((S(n-1) % m) * 10 + 1) % m       [if n is odd]

在Python中,这给我的笔记本电脑上的n = 10 ^ 16,m = 10 ^ 9,0.017s的运行时间,这完全在4s的截止日期之内.