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