模拟(60pts)

从小到大枚举$x$

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    LL a,b;
    cin>>a>>b;
    for(LL x=1;x<=100000000;x++)
    {
       if(a*x%b==1)
       {
           cout<<x;
           return 0;
       }
    }
    return 0;
}

扩展欧几里得( logn 100pts)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL exgcd(LL a,LL b,LL& x,LL& y) //扩展欧几里得求一组特定解
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    LL d=exgcd(b,a%b,y,x);
    y=y-a/b*x;
    return d;
}
int main()
{
    LL a,b;
    cin>>a>>b;
    LL x,y;
    exgcd(a,b,x,y);
    cout<<(x%b+b)%b; //求最小的非负数解
    return 0;
}