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

これが宿題であると仮定すると、ここにヒントがあります。二乗による指数化について読むと、擬似コードを含め、ソリューションを構築するために必要なすべてのものが得られます。

現在の実装では、の偶数値と奇数値を区別していません。これは、が2の累乗であるn場合にのみ正しい値です。nソリューションを拡張して、すべての人に役立つようにすることができますn（以下を参照）。

rem(x,n/2,p)とが偶数の戻り値を取得したらn、結果を2乗し、残りの2乗を取る必要があります。

これを拡張してn、の累乗だけでなく、すべてのに機能するように2、結果にさらに乗算し、xの奇数値の余りをとることができますn。