题解 P1082 【同余方程】

陈曦 · 2018-09-05 19:50:25 · 题解

仔细观察式子：ax≡1(mod b)

发现这就是此时x就是a模b意义下的逆元，即inv[a]=x;

不会求逆元的话，可以看我的博客

我们知道求单个逆元有两种方fa♂

所以我们先讲暴力（逃

1.暴力 80分

我校某退役选手的遗产

int main()//不想解释了，简单模拟
{
    long long int a,b,c,d=0;
    int j=0;
    scanf("%lld%lld",&a,&b);
    while(d!=1)
    {   
        ++j;d=a+d;
        if(d>b)
        {while(d>b)d-=b;}
    }
    write(j);
    return 0;
}

2.快速幂求逆元 10分

快速幂求逆元的原理很简单，就是费马小定理。

当 p 为素数，且a，p互质时：

a^{p-1}≡1(mod p)

a * a^{p-2}≡1(mod p)

所以a^(p-2)就是a在模p意义下的逆元，快速幂求出a^(p-2)即可。

快速幂算法最大的缺点就是模数必须为质数，所以这题gg。

inline long long ksm(int t,int i)//快速幂模板
{
    if(t==1)return i%m;
    if(t%2==0)
    return ksm(t>>1,i)*ksm(t>>1,i)%m;
    else
    return ksm(t>>1,i)*ksm(t>>1,i)*(i)%m;
}
int main()
{
    long long n;
    scanf("%lld%lld",&n,&m);
    write(ksm(m-2,n));
}

3.扩欧求逆元 100分

这很简单，就是

a*inv[a]≡1(mod p)

a*inv[a]-py=1

因为y是变量所以可以变成这样：

a*inv[a]+py=1

我们把inv[a]设成x，就变成了扩欧的标准式：

ax+by=1

然后就可以瞎搞了，至于不知道怎么瞎搞的同学，可以先点这里又是安利

#include<iostream>
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int k,x,y;
inline void read(int &x)//快读
{
    x=0; 
    int f=1; 
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') 
        f=-1; 
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }x*=f;
}
inline void exgcd(int a,int b)//扩欧模板，我用的是全局变量
{
    if(b==0)
    {x=1;y=0;return;}//当b=0,gcd(a,b)=a时，x=1,y=0。
    exgcd(b,a%b);
    k=x;x=y;
    y=k-a/b*y;
    return;
}
int main()
{
    int n,m;
    read(n),read(m);
    exgcd(n,m);
    printf("%d",(x+m)%m);
}

是不是很简单，点个赞就行了，谢谢