关于模乘法逆元的算法 - C++教室 - C++论坛

楼主

问题点数：0 回复次数：5

关于模乘法逆元的算法

要做一个模乘法逆元的程序,即已知A,M,求X,使得A*X=1 %M,其实很简单,可是我菜得很~~
希望会做的大哥大姐帮帮小弟~!!

搜索更多相关主题的帖子: 模乘法　算法　大姐　

第 2 楼

得分:0

题意不是很清楚！
A*X=1 %M？

长风破浪会有时，直挂云帆济沧海。 C++ing!

第 3 楼

得分:0

回复：（潇湘夜雨）题意不是很清楚！A*X=1 %M？

就是A乘X在模M的情况下为1

第 4 楼

得分:0

LZ的意思是这样吗
求X,s.t. (A*X)%M==1

If you shed tears when you miss the sun, you also miss the stars.

第 5 楼

得分:0

就是楼上的意思啦，但是楼主是要求第一个？还是要求一个范围内的

Viva,espana!

第 6 楼

得分:0

以下是引用che0804在2007-5-11 17:53:19的发言：
要做一个模乘法逆元的程序,即已知A,M,求X,使得A*X=1 %M,其实很简单,可是我菜得很~~

希望会做的大哥大姐帮帮小弟~!!

其实你说错了，这题不简单，A*X (mod M)=1 (mod M)是一个同余方程，等价于求满足A*X + M*Y=1的X，
这是一个不定方程，你可以参考一下数论的书，数学解法：大衍求一术，这个解法需要一套完整理论的支持，估计够你看上一阵子了，包括整除，剩余系，不定方程，同余，这个问题的解法在孙子定理(中国剩余定理)中也有利用到。
编程算法：扩展欧几里德算法