题目链接
题目大意：
图片说明
扩展欧几里得算法板子题
这里不能用费马小定理，因为不满足费马小定理的使用条件（b是一个质数，但是满足整数a不是b的倍数，因为题目保证有解gcd(a,b)=1)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b;
ll x,y;
ll ex_gcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    ll d=ex_gcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-(a/b)*y;
    return d;
}
int main(){
    cin>>a>>b;
    ex_gcd(a,b,x,y);
    x=(x+b)%b;//求最小正整数解，加b是因为x可能为负数 
    cout<<x<<endl;
    return 0;
}