오일러 정리를 구현하는 C++ 프로그램

이것은 오일러 정리의 구현을 보여주는 C++ 프로그램입니다. 모듈러 곱셈 역수가 존재하려면 숫자와 모듈러가 같은 소수여야 합니다.

알고리즘

Begin
   Take input to find modular multiplicative inverse
   Take input as modular value
   Perform inverse array function:
   modInverse(x + 1, 0);
   modInverse[1] = 1;
   for i = 2 to x
      modInverse[i] = (-(y / i) * modInverse[y mod i]) mod y + y
   return modInverse
End

예시 코드

#include <iostream>
#include <vector>
using namespace std;
vector<int> inverseArray(int x, int y) {
   vector<int> modInverse(x + 1, 0);
   modInverse[1] = 1;
   for (int i = 2; i <= x; i++) {
      modInverse[i] = (-(y / i) * modInverse[y % i]) % y + y;
   }
   return modInverse;
}
int main() {
   vector<int>::iterator it;
   int a, m;
   cout<<"Enter number to find modular multiplicative inverse: ";
   cin>>a;
   cout<<"Enter Modular Value: ";
   cin>>m;
   cout<<inverseArray(a, m)[a]<<endl;
}

출력

Enter number to find modular multiplicative inverse: 26
Enter Modular Value: 7
7