用 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

Krantik Chavan

更新日期：2019-07-30

422 次瀏覽

開啟你的 職業生涯

完成課程即可獲得認證

開始