【逆元】【数学】

· · 个人记录

逆元（inv）

1.什么是逆元

当求解公式：(a/b)\%m 时，因b可能会过大，会出现爆精度的情况，所以需变除法为乘法：

设c是b的逆元，则有b*c≡1 (mod\ m)；

则(a/b)\%m=(a/b)*1\%m=(a/b)*b*c\%m=a*c(mod\ m);

即a/b的模等于a*b的逆元的模；

逆元就是这样应用的；

2.求逆元的方法

(1).费马小定理

a^p≡a (mod\ p)

也写作a^{p-1}≡1 (mod\ p)

根据费马小定理，我们求解逆元的表达式

假如p是素数，且inv与p互质，那么 inv^{p-1}≡(1\%p) 根据逆元的定义我们可得的x*inv≡(1\%p) 得出乘法逆元inv=x^{p-2}

题目中的数据范围1<=x<=10^9，p=1000000007，p是素数；

所以x肯定就无法被p整除啊，所以最后就得出x^{p-2}为x的逆元啦。

复杂度O(logn)；

code:

const int mod=1000000007;
long long ksm(long long a,long long b) 
{
    if(b<0) return 0;
    long long ret=1;
    a%=mod;
    while(b) 
    {
        if(b&1) (ret*=a)%=mod;
        b>>=1;
        (a*=a)%=mod;
    }
    return ret;
}
long long inv(long long a) 
{
    return ksm(a,mod-2);
}

(2)扩展欧几里得算法求逆元

对于不完全为 0 的非负整数 a，b，gcd(a,b)表示 a，b 的最大公约数，必然存在整数对 x,y ，使得 gcd(a,b)=ax+by。

求解 x，y的方法

百度百科-乘法逆元中有这样一个例子:

例如：4关于1模7的乘法逆元为多少？
4X≡1 mod 7
这个方程等价于求一个X和K，满足
4X=7K+1
其中X和K都是整数。
求x，k就是扩展欧几里得算法了吧~
可扩展欧几里得求逆元ax≡1(mod n)其中a，n互质；

复杂度：O(logn)；

code:

#define ll long long
ll exgcd(ll a, ll b, ll &x, ll &y) 
{
    if (b==0) {x=1,y=0;return a;}
    else 
    {
        ll r=exgcd(b,a%b,y,x);
        y-=x*(a/b);
        return r;
    }
}
ll inv(ll a, ll n) 
{
    ll x,y;
    exgcd(a,n,x,y);
    x=(x%n+n)%n;
    return x;
}

附P1082 同余方程 AC代码：

//另一种风格的exgcd，跟上面是等价的

#include <iostream>  
#include <cstdio> 
using namespace std;
int a,b,x,y,k;
void exgcd(int a,int b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);
    k=x;
    x=y;
    y=k-a/b*y;
    return;
}
int main()
{
    scanf("%d%d",&a,&b);
    exgcd(a,b);
    printf("%d",(x+b)%b);
}

(3)线性求逆元

已知一个质数M，求出1→n中每个数关于模M的逆元，时间复杂度O(n) 公式：

inv[i]=(M-\lfloor{M/i}\rfloor)\times inv[M\%i]\%M

推导如下：

设i\in[1,n],t=\lfloor{M/i}\rfloor,k=M\%i

\qquad\qquad\qquad\qquad\qquad\because t\times i+k\equiv0\ (mod\ M) \qquad\qquad\qquad\qquad\qquad\therefore -t\times i\equiv k\ (mod\ M)

同除i\times k \qquad\qquad\Rightarrow -t\times inv[k]\equiv inv[i]\ (mod\ M)

再将t,k代入

\qquad\qquad\qquad\Rightarrow -\lfloor{M/i}\rfloor\times inv[M\%i]\equiv inv[i]\ (mod\ M)

将mod\ M代入转化为等式

\qquad\qquad\qquad\Rightarrow inv[i]=(M-\lfloor{M/i}\rfloor)\times inv[M\%i]\%M

推导完毕

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3000010;
int inv[N]={0,1},n,p;
int main()
{
    scanf("%d%d",&n,&p);
    puts("1"); 
    for(int i=2;i<=n;i++)
    {
        inv[i]=(ll)(p-p/i)*inv[p%i]%p;
        printf("%d\n",inv[i]);
    }
    return 0;
}