How to calculate pow(2,n) when n exceeds 64 in c++?

Question

So, I am new to programming in c++ and i came across this question where i need to calculate pow(2,n)/2 where n>64 ?

i tried using unsigned long long int but as the limit of the c++ is only 2^64. So is there any method to calculate this.

Edit:

 1 < n < 10^5

The result of the expression is used in further calculation

The question is asked on online platform.So, i cant use libraries like gmp to handle large numbers.

Question

你给出与阵列甲的大小Ñ。如果元素Ai的值（Ai）大于或等于Ki，则称该元素为带电的。Ki是由元素Ai组成的数组A的子集的总数。 数组的总电荷值定义为数组mod（10 ^ 9）+7中存在的所有带电元素的总和。 您的任务是输出给定数组的总费用值。

Answer 1

这里有一个重要的细节是，你没有被要求计算2 ^ñ的巨大ñ。相反，系统要求您为大n 计算2 ⁿ mod 10 ⁹ + 7，这是一个不同的问题。

例如，假设您要计算2 ⁷⁰ mod 10 ⁹ +1。请注意，2 ⁷⁰不适合64位机器字。但是，2 ⁷⁰ = 2 ³⁰ ·2 ³⁵，而2 ³⁵确实适合64位机器字。因此，我们可以进行以下计算以获得2 ⁷⁰ mod 10 ⁹ + 7：

2 ⁷⁰（模组10 ⁹ + 7）

= 2 ³⁵ ·2 ³⁵（mod 10 ⁹ + 7）

=（2 ³⁵ mod 10 ⁹ + 7）·（2 ³⁵ mod 10 ⁹ + 7）mod 10 ⁹ + 7

=（34359738368 mod 10 ⁹ + 7）·（34359738368 mod 10 ⁹ + 7）mod 10 ⁹ + 7

=（359738130·359738130）mod 10 ⁹ + 7

= 129411522175896900 mod 10 ⁹ + 7

= 270016253

更一般而言，通过使用重复平方，您可以以适合64位整数的方式为任何n值计算2 ⁿ mod 10 ⁹ + 7。

希望这可以帮助！

Answer 2

认真进行数值工作的常用方法是重写公式。您可以存储log(x)而不是x，以后再需要x时通常会在上下文中不需要任何这些数字。