C++の素数のmodの下で力の力を見つける

この問題では、4つの値A、B、C、M（素数）が与えられます。私たちの仕事は、素数のmodの下で力の力を見つけることです。

（A ^（B ^ C））（mod M）の値を見つける必要があります。

問題を理解するために例を見てみましょう

入力

A = 3, B = 6, C = 2, M = 11

出力

3

説明

（A ^（B ^ C））=（3 ^（6 ^ 2））=（3 ^（36））（mod 11）=3

ソリューションアプローチ

この問題の簡単な解決策は、（A ^（B ^ C））の値を直接計算することです。これは、最初に（B ^ C）の値を計算し、次に（A ^（B ^ C））を計算することによって行われます。そのmodを取る。 （B ^ C）は、タスクになる可能性のある巨大なフィギュアの保存になります。そして、計算はオーバーフローにつながる可能性があります。

したがって、より効率的なアプローチは、フェルマーの小定理を使用して値を見つけることです。

定理は、

a^(m-1) = 1 (mod M) where m is a prime number.

これを使用して、問題のbcをいくつかの形式に変換します

x *（M-1）+ y、指定されたMの値。

フェルマーの定理を使用すると、部分A ^（x *（M-1））は1になります。

これにより、計算がに減り、A ^y の値が見つかります。 。

yの値は、次のように計算できます。

B ^c =x *（M-1）+ y

これにより、B ^c を除算したときにyが余りになります。 （M-1）、

したがって、y =B ^c ％（M-1）

これにより、見つける必要があるため、結果が非​​常に簡単になります。

(A ^ ((B^C) %( M-1)) % M

ソリューションの動作を説明するプログラム

例

#include<iostream>
using namespace std;
int calcPowerMod(int x, int y, int p) {
   int powMod = 1;
   x = x % p;
   while (y > 0) {
      if (y & 1)
         powMod = (powMod*x) % p;
      y /=2; // y = y/2
      x = (x*x) % p;
   }
   return powMod;
}
int findPowerOfPowerMod(int A, int B, int C, int M) {
   return calcPowerMod(A, calcPowerMod(B, C, M-1), M);
}
int main() {
   int A = 3, B = 6, C = 2, M = 11;
   cout<<"The power of power under modulo is "<<findPowerOfPowerMod(A, B, C, M);
   return 0;
}

出力

The power of power under modulo is 3