乘法逆元算法

2019-04-13 15:25发布

站内文章 / 模拟电子
10725 0 1800
若ax ≡ 1 mod b, 则称x是a关于模b的乘法逆元，其中a、b互质。
ax ≡ 1 mod b等价于求整数x满足ax%b=1，
例1：求3关于模8的乘法逆元：1 = 3*3-8，因此，3关于模8的乘法逆元为3； 例2：求5关于模14的乘法逆元：1=5*3-14，因此，5关于模14的乘法逆元为3。 题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1256
给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N 且 K * M % N = 1，如果有多个满足条件的，输出最小的。 Input 输入2个数M, N中间用空格分隔（1 <= M < N <= 10^9) Output 输出一个数K，满足0 < K < N且K * M % N = 1，如果有多个满足条件的，输出最小的。 Input示例 2    3 Output示例 2
 C++代码实现： #include #include #include using namespace std; typedef long long ll; ll EXGCD(ll a, ll b, ll &x, ll &y) { if(b == 0) { x = 1; y = 0; return a; } else { int z = EXGCD(b, a%b, x, y); int temp = x; x = y; y = temp-a/b*y; return z; } } int main() { ll m, n, x, y, K; while(cin >> m >> n) { EXGCD(m, n, x, y); K = (x+n)%n; cout << K << endl; } return 0; }  

热门文章