如何求(2^n)%p的结果？
我陷入了一个问题，要求找到 (2^n)%p，其中 n 是 10^36 阶的一个非常大的数，p 是素数。如何快速完成此操作？？？这里 ^ 表示幂 我遇到了这个算法，但它给出了堆栈溢出，因为 10^36 非常大
double power(double a,double b,int mod)
{
if (b==0)
return 1;
else if(b%2==0)
return square(power(a,b/2,mod))%mod;
else return power(a,b-1,mod)%mod;
}
他们还有其他方法或对此的改进吗？
I was stuck in a question which asked to find (2^n)%p where n is a very large number of the order 10^36 and p is a prime.How to do this quickly???Here ^ means power
I came across this algorithm but it gives stack overflow as 10^36 is very large
double power(double a,double b,int mod)
{
if (b==0)
return 1;
else if(b%2==0)
return square(power(a,b/2,mod))%mod;
else return power(a,b-1,mod)%mod;
}
Is their any other way or an improvement on this??
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您可以使用分而治之的方法。
基本思想如下：
2^8 = (2^4)^2
2^4 = (2^2)^2
因此，您需要计算 2^2 一次并将其平方以获得 2^4。然后将结果平方得到 2^8 等等。
如果 n 是 2 的幂，演示的情况就完美。但是，可以将任何像这样的幂分解为 2 或 3 个子问题。
例如，如果 n = 20，它将分解为 (2^10)^2。
如果n = 21，它将分解为(2^10)^2 * 2。
因此，根据幂的奇数和偶数值，您可以将其分解为分量。
希望插图是清楚的。
You can use divide and conquer approach.
Here is the basic idea:
2^8 = (2^4)^2
2^4 = (2^2)^2
Therefore, you would need to calculate 2^2 once and square it to get 2^4. Then Square that result to get 2^8 and so on.
The demonstrated case, works perfectly if n is a power of 2. However, It's possible to break any powers like this into 2 or 3 sub-problem.
For example, if n = 20, it would break to (2^10)^2.
if n = 21, it would break to (2^10)^2 * 2.
Therefore, depending on odd and even value for the power, you could dissolve it into component.
Hope the illustration was clear.
在这种情况下，Python 可以帮助您。在Python中你不需要关心数据类型的范围，你只要给出数据的值Python就会自动调整变量的数据类型。
In this case Python can help you. In python you need not to take care about the range of the data type, you just give the value of data python will adjust the data type of the variables automatically.