【NOIP2012 提高组 day2】同余方程

题目

---

题解

–对于ax≡1(mod b) 可以转化成 ax=by+1,即ax-by=1
现在来一个扩欧就能搞定

---

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAXN=1;

long long a,b;
long long x,y;

void exgcd(long long a,long long b,long long &x,long long &y){
    if(!b){
        x=1;
        y=0;
        return ;
    }
    exgcd(b,a%b,x,y);
    long long z=x;
    x=y;
    y=z-y*(a/b);
}

int main(){
//  freopen("mod.in","r",stdin);
//  freopen("mod.out","w",stdout);
    cin>>a>>b;
    exgcd(a,b,x,y);
    while(b&&x-b>0)
        x-=b;
    while(b&&x<0)
        x+=b;
    cout<<x;
    return 0;
}