51nod 125乘法逆元 (扩展欧几里得)
发布日期:2022-03-11 15:03:39 浏览次数:8 分类:技术文章

本文共 1231 字,大约阅读时间需要 4 分钟。

给出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
#include
#include
using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define maxn 1000005#define MOD 1000000007#define mem(a , b) memset(a , b , sizeof(a))#define LL long long#define ULL long longconst long long INF=0x3fffffff;void exc_gcd(LL a , LL b , LL &d , LL &x , LL &y){ if(b == 0) { x = 1 ; y = 0 ; d = a; } else { exc_gcd(b ,a % b , d , y , x); y -= x * (a/b); }}//ofstream ofile;int main(){ int n , m; while(scanf("%d %d",&m , &n) != EOF && m) { LL x , y , d; exc_gcd(m , n , d , x , y); x /= d; y /= d; LL t1 = n / d; LL t2 = m / d; x = (x % t1 + t1) % t1; cout << x << endl; } return 0;}

转载于:https://www.cnblogs.com/yfceshi/p/7247338.html

转载地址:https://blog.csdn.net/weixin_30267785/article/details/99192405 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:ViewPager禁止拖动
下一篇:敏捷开发的宣言和原则

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年07月15日 11时28分42秒