乘法逆元 51Nod - 1256——同余定理+逆元(乘法逆元) (拓展欧几里得算法求逆元)

比眉伴天荒 2022-05-19 13:41 268阅读 0赞

给出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，如果有多个满足条件的，输出最小的。  
**Sample Input**  
2 3  
**Sample Output**  
2

--------------------

用拓展欧几里得算法求得逆元

--------------------

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<string>
    #include<algorithm>
    #include<iostream>
    #include<map>
    #include<set>
    #include<vector>
    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;
        }
        ll r=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return r;
    }
    ll inv(ll a,ll mod)
    {
        ll x,y;
        ll d=exgcd(a,mod,x,y);
        if(d==1)    return (x%mod+mod)%mod;
        return -1;
     } 
    
    int main()
    {
        ll m,n;
        while(~scanf("%lld %lld",&m,&n))
        {
            printf("%lld\n",inv(m,n));
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，268人围观）

还没有评论，来说两句吧...

相关阅读

相关乘法逆元整理

乘法逆元 1.费马小定理 > 如果 $ a,p $ 互质，那么 $ a^\{p-1\} ≡ 1(mod p) $ > 又由逆元方程知 $ a\*x ≡ ...

约定不等于承诺〃/ 2024年04月20日 10:25/ 0 赞/ 77 阅读

相关数论-同余与逆元

文章目录同余一元线性同余方程逆元逆元与除法取模例题 HDU-5976 同余 -----------

曾经终败给现在/ 2022年11月25日 14:30/ 0 赞/ 183 阅读

相关【算法与数据结构】——乘法逆元

定义若在mod p意义下，对于一个整数a，有a\b≡1(mod p)，那么这个整数b即为a的乘法逆元，同时a也为b的乘法逆元一个数有逆元的充分必要条件是gcd(

落日映苍穹つ/ 2022年09月04日 04:53/ 0 赞/ 172 阅读

相关 51nod 1256 乘法逆元（exgcd）

题目链接： [点击打开题目链接][Link 1] 题解： K∗MmodN=1等价于 K∗M=N∗X\+1。即 K∗M\+N∗(−X)=1。可以用扩展欧几里德，求

柔光的暖阳◎/ 2022年06月15日 02:36/ 0 赞/ 238 阅读

相关逆元详解求逆元的方法汇总

[基础知识][Link 1] [求乘法逆元的几种方法][Link 2] [逆元详解][Link 3] [Link 1]: http://blog.csdn.net/fe

秒速五厘米/ 2022年06月13日 05:45/ 0 赞/ 228 阅读

相关详解--乘法逆元

今天我们来探讨逆元在ACM-ICPC竞赛中的应用，逆元是一个很重要的概念，必须学会使用它。对于正整数![20140613102654328][]和![20140613

怼烎@/ 2022年06月11日 07:48/ 0 赞/ 364 阅读

相关扩展欧几里德定理--------乘法逆元

给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K \ M % N = 1，如果有多个满足条件的，输出最小的。 Input 输入2个数M,

矫情吗；*/ 2022年06月11日 05:25/ 0 赞/ 206 阅读

相关乘法逆元 51Nod - 1256——同余定理+逆元(乘法逆元) (拓展欧几里得算法求逆元)

给出2个数M和N(M < N)，且M与N互质，找出一个数K满足0 < K < N且K \ M % N = 1，如果有多个满足条件的，输出最小的。 Input 输入2个数

比眉伴天荒/ 2022年05月19日 13:41/ 0 赞/ 269 阅读

相关 A/B——同余定理+逆元（除法逆元）

同余定理: 数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(modm)

太过爱你忘了你带给我的痛/ 2022年05月19日 11:18/ 0 赞/ 289 阅读

相关扩展欧几里得+求解逆元

在为扩展前，什么是欧几里得算法？？欧几里得又称辗转相除法，用于计算两个整数a,b的最大公约数（最大公约数：指两个或多个整数共有约数中最大的一个）其计算原理依赖于下面的定理：

ゝ一世哀愁。/ 2022年05月16日 22:26/ 0 赞/ 194 阅读