同余方程

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 672 字

求关于x的同余方程a*x≡1的最小正整数解

一本通
例

正文

/*
原题：同余方程 (NOIP 2012 提高组)
题意：求关于 x 的同余方程 a*x ≡ 1 (mod b) 的最小正整数解。
思路：即求 a 在模 b 下的乘法逆元；用扩展欧几里得解方程 a*x+b*y=1。
      数据保证有解，将解对 b 取模并归一到最小正整数即可。
复杂度：时间 O(log b)，空间 O(1)。
易错点：逆元结果需归一到 [0,b)，且要求正整数（不会为 0）；负数要正确取正。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
// 扩展欧几里得：返回 gcd(a,b)，并求 a*x+b*y=gcd
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll x1, y1;
    ll g=exgcd(b, a%b, x1, y1);
    x=y1;
    y=x1-(a/b)*y1;
    return g;
}
int main(){
    ll a, b;
    cin>>a>>b;
    ll x, y;
    exgcd(a, b, x, y);
    x=((x%b)+b)%b;
    if(x==0){
        x+=b;
    }
    cout<<x<<"\n";
    return 0;
}

同余方程

正文

一本通·提高篇的其它内容