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

Question

我想在 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);
}

Answer 1

假设这是家庭作业，这里有一个提示:继续阅读 exponentiation by squaring ，它为您提供构建解决方案所需的一切，包括伪代码。

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

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

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