我想在o（nlogn）中找到（x^n除以p）的提醒，n=2^k；
我写的，但不是真的，你能帮我吗？
rem(int x,int n,int p){
if (n==1)
return x%p;
else
return rem(x,n/2,p);
}
最佳答案
假设这是家庭作业，这里有一个提示：read onexponentiation by squaring，它为您提供构建解决方案所需的一切，包括伪代码。
您当前的实现不区分奇偶值n，只有当n是二的幂时才正确您可以扩展您的解决方案以适用于所有n（请参见下文）。
当返回值rem(x,n/2,p)且n为偶数时，应将结果平方，并取平方的余数。
您可以将其扩展为对所有n都有效，而不仅仅是对2的幂，方法是将结果乘以x并对n的奇数值取余数。
关于algorithm - 在O(nlogn)中寻找(x ^ n除数p)的提醒，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10142222/