洛谷——P3811 【模板】乘法逆元

P3811 【模板】乘法逆元

线性求逆元

逆元定义：若$a*x\equiv1 (\bmod {b})$，且$a$与$b$互质，那么我们就能定义: $x$为$a$的逆元，记为$a^{-1}$，所以我们也可以称$x$为$a$的倒数，

所以对于$\frac{a}{b} (\bmod {p})$ ，我们就可以求出$b$在$\bmod {p}$下的逆元，然后乘上$a$，再$\bmod {p}$，就是这个乘法逆元的值了。

一、exgcd求逆元(O(l$og_n$))

这个就是利用拓欧求解线性同余方程$a*x \equiv c (\bmod {b})$

的c=1的情况。我们就可以转化为$a*x + b*y = 1$，求解这个方程的解。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

using namespace std;

void exgcd(ll a,ll b,ll &x,ll &y){

    if(!b){

        x=,y=;

        return;

    }

    exgcd(b,a%b,x,y);

    ll tmp=x;

    x=y;

    y=tmp-a/b*y;

}

int n,p;

int main()

{

    scanf("%d%d",&n,&p);

    for(int i=;i<=n;i++){

        ll x,y;

        exgcd(i,p,x,y);

        x=(x%p+p)%p;

        printf("%lld\n",x);

    }

    return ;

}

Exgcd

二、快速幂+费马小定理

费马小定理：若$p$为素数，$a$为正整数，且$a,p$互质。 则有$a^{p-1} \equiv 1 (\bmod {p})$。

$a*x\equiv 1(\bmod {b})$

$a*x\equiv a^{p-1} (\bmod {b})$
$x \equiv a^{p-2} (\bmod {b})$

有点儿慢。。。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

using namespace std;

int n,p;

ll pow(int a,int b,int mod){

    ll s=,t=a%mod;

    for(;b;b>>=,t=1ll*t*t%mod)

        if(b&) s=1ll*s*t%mod;

    return s;

}

int main()

{

    scanf("%d%d",&n,&p);

    for(int i=;i<=n;i++){

        printf("%lld\n",pow(i,p-,p));

    }

    return ;

}

快速幂

三、线性递推求逆元

如何递推呢？

大佬说：推一下就好了嘛

蒟蒻（我）：。。。=_=

首先$1^{-1}\equiv1(modp)$

设$p=k\times i+r$，$r < i$，$1< i < p$

那么$k\times i+r \equiv 0 (mod p)$

方程同乘$i^{-1},r^{-1}$得

$k\times r^{-1}+i^{-1} \equiv 0 (mod p)$

移项得：$i^{-1}\equiv -k\times r^{-1} (mod p)$

即$i^{-1}\equiv\lfloor{\frac{p}{i}}\rfloor \times (p mod i)^{-1} (mod p)$

也就是下面这一行代码：

inv[i]=(p-p/i)*inv[p%i]%p;

奉上代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define ll long long

#define N 10101010

using namespace std;

int n,p;

ll inv[N];

int main()

{

    scanf("%d%d",&n,&p);

    inv[]=;

    printf("1\n");

    for(int i=;i<=n;i++){

        inv[i]=(p-p/i)*inv[p%i]%p;

        printf("%lld\n",inv[i]);

    }

    return ;

}