51nod 1256 乘法逆元（exgcd）

柔光的暖阳◎ 2022-06-15 02:36 222阅读 0赞

题目链接：  
[点击打开题目链接][Link 1]

题解：  
K∗MmodN=1等价于 K∗M=N∗X\+1。即 K∗M\+N∗(−X)=1。  
可以用扩展欧几里德，求出K和（−X）；  
而K要是正整数的，即如果K为负整数，则需要将之化正，即与负数取模同理，将K加上N，直至K>0为止，所得的数即为最小的乘法逆元；  
如果K为正整数，则直接输出即可。

代码：

#include <bits/stdc++.h>
    using namespace std;
    int exgcd(int a,int b,int &x,int &y)
    {
        if(b==0)
        {
            x=1;
            y=0;
            return a;
        }
        int res=exgcd(b,a%b,x,y);
        int t=x;x=y;y=t-(a/b)*y;
        return res;
    }
    int main()
    {
        int n,m;
        int x,y;
        cin>>m>>n;
        exgcd(m,n,x,y);
        while(x<0){
            x+=n;
        }
        cout<<x<<endl;
        return 0;
    }

/*
    总结：求逆元的方法
    在 mod 的情况下，(a*b/c)%mod不能直接/c来求，需要找到一个数inv使得 inv*c % mod =1.这样(a*b/c)%mod = (a*b*inv)%mod 
    性质：逆元是积性函数，存在a*b=c,那么 inv[c]=inv[a] * inv[c] %mod 
    1, 暴力循环找解
    2，费马小定理的解法：mod是质数才能用
    3，利用欧几里得扩展来求。
    欧几里得扩展是用来解决 ax +by=gcd(a,b)这样的式子
    这时候取 b=mod，你可以写成这样，ax=gcd(a,b)-by
    推导出 a*x % mod=gcd(a,b)%mod
    所以只要gcd(a,b)%mod==1时就可以使用这种方法来求逆元 
    4，利用神奇的推导，O(n)  求出 1~n的所有逆元(参考下面的 ini()) 
    void ini()  //O(n)求逆元 
    {
        inv[1] = 1;
        for(int i = 2;i <= N;i ++)
        {
            inv[i] = (mod - mod/i) * inv[mod % i] % mod;
        }
    //  for(int i=1; i<=10;i++)
        //cout<<inv[i]<<endl;
    }
    5, 利用逆元函数是完全积性函数的性质,O(logN)求单个数的逆元 
    */

[Link 1]: http://www.51nod.com/onlineJudge/userProblemSubmitList.html#!userId=12837&problemId=1256