给出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
思路:
对于正整数和
。假设有
。那么把这个同余方程中
的最小正整数解叫做
模
的逆元。
逆元一般用扩展欧几里得算法来求得,假设为素数。那么还能够依据费马小定理得到逆元为
。
推导步骤例如以下
#include#include #include #include #include #include #include #include #include #include #include