计算2的k次方
计算2的k次方
提问于 2019-06-11 16:59:43
我正在解决一个问题，基本思想是计算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);
}此幂函数超出其范围。任何好的解决方案。
回答 2
Stack Overflow用户
发布于 2019-06-11 17:04:59
您需要使用将幂除以2的思想。
long bigmod(long p,long e,long M) {
if(e==0)
return 1;
if(e%2==0) {
long t=bigmod(p,e/2,M);
return (t*t)%M;
}
return (bigmod(p,e-1,M)*p)%M;
}
while(t-->0){
long k = scan.nextInt();
long ans = bigmod(2, k, 1000000007);
System.out.println(ans);
}你可以从这里获得关于这个想法的详细信息：https://www.geeksforgeeks.org/how-to-avoid-overflow-in-modular-multiplication/
Stack Overflow用户
发布于 2019-06-11 17:29:07
由于long的大小为8字节，且为signed数据类型，因此long数据类型的范围为-(2^63) to (2^63 - 1)。因此，要存储2^100，必须使用另一种数据类型。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/56540040
复制相关文章
相似问题