gpt4 book ai didi

java - 计算 2 的 k 次方

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:31:34 25 4
gpt4 key购买 nike

我正在解决一个问题和计算某个 k 的 2 次方的基本思想。然后乘以10。结果应该是计算值mod10^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 函数超出了它的范围。任何好的解决方案。

最佳答案

基本上,f(g(x)) mod Mthe 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 的递归解决方案展示了一种优雅的方式来做到这一点。

关于java - 计算 2 的 k 次方,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56540040/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com