java - 计算 2 的 k 次方

Question

我正在解决一个问题和计算某个 k 的 2 次方的基本思想。然后乘以10。结果应该是计算值mod 10^9+7。

给定约束1≤K≤10^9

我为此使用 java 语言。我使用了“Math.pow”函数，但 2^10000000 超出了它的范围，我不想在这里使用“BigInteger”。计算如此大的值的任何其他方法。

实际问题是:

对于每个有效的 i，编号为 i 的符号的一侧写有整数 i，另一侧写有 10K−i−1。

现在，Marichka 想知道 - 有多少路标(两边总共)有两个不同的十进制数字？由于这个数字可能很大，计算它模 10^9+7。

我正在使用这种 pow 方法，但这不是一种有效的方法。解决这个问题的任何建议。

我原来的解决方案:

/* package codechef; // don't place package name! */

import java.util.*;
class Codechef
{
 public static void main (String[] args) throws java.lang.Exception
{
    Scanner scan = new Scanner(System.in);
    int t = scan.nextInt();
    while(t-->0){
        long k = scan.nextInt();
        long mul=10*(long)Math.pow(2, k-1);
        long ans = mul%1000000007;

        System.out.println(ans);
    }
  }
}

在举了一些例子之后，我发现这个 pow 解决方案适用于小约束但不适用于大约束。

while(t-->0){
        long k = scan.nextInt();
        long mul=10*(long)Math.pow(2, k);
        long ans = mul%1000000007;

        System.out.println(ans);
    }

这个 pow 函数超出了它的范围。任何好的解决方案。

Answer 1

基本上，f(g(x)) mod M 是 the same作为 f(g(x) mod M) mod M。由于求幂只是很多乘法，您可以将单个求幂分解为许多乘法，并在每一步应用模数。即

10 * 2^5 mod 13

与

相同

10
* 2 mod 13
* 2 mod 13
* 2 mod 13
* 2 mod 13
* 2 mod 13

到目前为止，您可以通过不分解求幂来压缩循环；也就是说，这将再次给出相同的答案:

10
* 4 mod 13
* 4 mod 13
* 2 mod 13

Faruk 的递归解决方案展示了一种优雅的方式来做到这一点。