algorithm - 在 O(nlogn) 中找到 (x^n 除 p) 的提醒

Question

我想在 O(nlogn), n=2^k; 中找到 (x^n 除 p) 的提醒；我写了这个，但它不是真的，你能帮帮我吗？

rem(int x,int n,int p){

if (n==1)
 return x%p;
else
 return rem(x,n/2,p);
}

Answer 1

假设这是作业，这里有一个提示：阅读通过平方求幂，它为您提供构建解决方案所需的一切，包括伪代码。

您当前的实现不区分 的偶数和奇数值n，只有当n是 2 的幂时才正确。您可以扩展您的解决方案以适用于所有人n（见下文）。

当你得到一个返回值rem(x,n/2,p)并且n是偶数时，你应该将结果平方并取平方的余数。

您可以将其扩展为适用于所有n，不仅是 的幂2，方法是另外将结果乘以 并对x的奇数值取余数n。