c++ - 为大 N 计算 2^n

Question

我想用 mod 操作计算 N 的大值的 2^N，即高达 10^9。使用了迭代方法，但输入 10^8 需要花费大量时间。

for(long i=1;i<=n;i++){ res=(res*2)%1000000007 }

计算 n=10^8 及以上需要时间。

Answer 1

您可以通过平方和乘以 2 来提高速度 - 例如 2^4 可以达到 2*2 => 4、4*4 => 16。

从 2 开始。如果 N 是偶数，则将你所拥有的平方并将 N 减半。如果 N 是奇数，则乘以 2 并减少 N。随时应用模数。

您可能必须小心平方不会溢出。