11.19鲜花-526互联

第一天学数论

学了学exgcd和逆元

找了普及组OJ上的几道简单题来做

同余方程

拓展欧几里得板子题

对于形似\(a\times x=1\pmod{b}\)的同余方程

可以转化成\(a\times x+b\times y=1\)

然后就可以通过\(exgcd\)直接求解

点击查看代码

#include<bits/stdc++.h>
#define lC q<<1
#define rC q<<1|1
#define int long long
#define INF 0x66ccff0712
#define endl "\n"
#define maxm 0x66ccff
#define maxn 0x6cf 
#define mid ((l+r)>>1)
#define void inline void
using namespace std;
inline int read(){
    int s = 0,w = 1;char ch = getchar();
    while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}
    while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}
    return s*w;
}
inline int gcd(int a,int b){
    return __gcd(a,b);
}
inline int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,x,y);
    int z=x;x=y,y=z-y*(a/b);
    return d;
}
inline int exmod(int a,int b){
    int d,x,y;
    d=exgcd(a,b,x,y);
    if(d==1) return(x%b+b)%b;
    else return -1;
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    int a,b;
    cin>>a>>b;
    cout<<exmod(a,b);
}