Question

乘法逆元 C++ A=B mod n其中B，n已知，如何求A？要求用C++写出来，急用！！！回答的好再加分

Answer 1

#include <iostream>
using std::cin;
using std::cout;
using std::endl;
int Euclid(int,int,int,int);
int main()
{
int n,u;
cout<<"please input n and u"<<endl;
cin>>n;
cin>>u;
cout<<(Euclid(n,u,0,1) + n) % n<<endl;
system("pause");
return 0;
}

int Euclid(int n, int u, int b1, int b2)
{
int q; //商
q = n / u;
int r; //余数
r = n % u;
if(0 != r)
{
int t;//中间变量
n = u;
u = r;
t = b2;
b2 = b1 - q * b2;
b1 = t;
return Euclid(n,u,b1,b2);
}
else
{
if(1 != u)
cout<<"Error"<<endl;
else
return b2;
}
return 0;
}
这是求u模n的逆元的

追问

cin>>A;
for(int i=0;i<e1;i++) B=B*A%n;核心部分用它就能完全解决问题了，哪有你这么麻烦的。。。。。。。。。。。。。

Answer 2

根据乘模性质！