我坚持使用算法,其中我需要生成n个数字’1′,其中n <= 10 ^ 16且n> = 1.我在BigInteger的for循环中成功生成了n个,因为long和string都无法保存.但问题是这个时间限制是4秒,并且对于n> 10 ^ 5需要超过4秒.这显然是在O(n)中产生的.我认为没有必要使用相应的代码.我发现很多网站但找不到任何解决方案.任何更好的算法都会有所帮助.谢谢.
编辑：这是一个拼图问题,其中n和m输入,我需要打印111 …(n次)mod m,其中限制是1≤N≤10^ 16和2≤M≤10^ 9.例如,
假设n = 3& m = 3然后打印111％3,其等于0假设n = 5& m = 18然后打印11111？等于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));
}

解决方法:

如果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的截止日期之内.