51nod 125乘法逆元（扩展欧几里得）-白红宇的个人博客

发布日期：2022-03-11 15:03:39 浏览次数：6 分类：技术文章

本文共 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演示样例

思路：

对于正整数和。假设有。那么把这个同余方程中的最小正整数解叫做模的逆元。

逆元一般用扩展欧几里得算法来求得，假设为素数。那么还能够依据费马小定理得到逆元为。

推导步骤例如以下

#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禁止拖动

下一篇：敏捷开发的宣言和原则

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章