用 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

更新日期：2019-07-30

422 次浏览

开启你的 职业生涯

完成课程即可获得认证

开始
广告