逆元 | 高性能架构探索

乘法逆元是用来：

定义：

若a*x≡1(mod b),且a与b互质，我们定义x是a的逆元，记为a^(-1)，所以也可以说x是a在mod b意义下的倒数

所以对于a/b(mod p)，我们可以先求出b在mod p下的逆元，然后乘a再mod p就是这个分数的值了

1.拓展欧几里得求逆元

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

2.快速幂求逆元

这个做法运用到了费马小定理

自己去百度啊哈哈哈哈

若p为素数，a为正整数，且a、p互质。则有a^(p-1)≡1(mod p)。

然后代入原式，神奇的事发生了

a*x≡1(mod p)

a*x=a^(p-1) (mod p)

x=a^(p-2) (mod p)

然后我们求a^(p-2)(mod p)就是它的逆元啦

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,p;
int fpm(ll x,ll y)//快速幂
{
    x%=p;
    ll ans=1;
    while(y)
    {
        if(y&1)ans=(ans*x)%p;
        y>>=1;
        x=x*x%p;
    }
    return ans;
}
int main()
{
    cin>>n>>p;
    for(int i=1;i<=n;i++)
    {
        printf("%lldn",fpm(i,p-2));
    }
}

3.线性算法

以上算法针对于求单个逆元，但是有一长串的时候，你就TLE了，所以，聪明的大佬们研发的线性算法出现（nb!!!!）

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,p;
ll inv[3000005];
int main()
{
    cin>>n>>p;
    inv[1]=1;
    printf("%lldn",inv[1]);
    for(int i=2;i<=n;i++)
    {
        inv[i]=(p-p/i)*inv[p%i]%p;
        printf("%lldn",inv[i]);
    }
}

学会了求逆元后，我们就可以学学其他interesting的东西——中国剩余定理

反正我不学，略略略

原文链接: https://www.cnblogs.com/zust-lms/p/12300075.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/328877

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

逆元

相关推荐