我被困在一个要求找到 (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;
}
他们有任何其他方式或对此有所改进吗？
您可以使用分而治之的方法。
这是基本思想：
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。
因此，根据功率的奇偶值，您可以将其分解为组件。
希望插图清楚。
在这种情况下， Python可以帮助您。在python中你不需要关心数据类型的范围，你只需给数据的值python会自动调整变量的数据类型。