不是很清楚这个应该怎么翻译,暂且就叫模乘法逆吧,定义是整数a在整数m下的模乘法逆为x,
有ax=(mod m)
x的范围要在0,1,2,...,m-1之间
举个例子就能说明这个问题啦
Given two integers ‘a’ and ‘m’, find modular multiplicative inverse of ‘a’ under modulo ‘m’.
给定两个整数a和m,找到a在m下的模乘法逆
例1
a为3,m为11
输入: a = 3, m = 11
输出: 4
因 (4*3) mod 11 = 1, 4 是 3 的模乘法逆
有人可能会说 15 也是3的模乘法逆,因为 "(15*3) mod 11"的结果也是 1, 但是 15 不在范围 {0, 1, 2, ... 10}中, 所以15不是
例2
输入: a = 10, m = 17
输出: 12
因 (10*12) mod 17 = 1, 12 是 10 的模乘法逆
网友评论