求关于xx的同余方程 ax≡1(modb) 的最小正整数解。
输入格式：
一行，包含两个正整数 a,b，用一个空格隔开。
输出格式：
一个正整数 x，即最小正整数解。输入数据保证一定有解。
看一下这个方程ax≡1(modb) ，的意思是ax-1是b的倍数，我们设ax-1是b的-y倍，那么就是ax-1=-yb，移项得：ax+by=1，这不就是扩展欧几里得吗？
把x、y解出来，然后再用一下求最小正整数解就好了
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #define REP(i,k,n) for(long long i=k;i<=n;i++) #define in(a) a=read() using namespace std; inline long long read(){ long long x=0,f=1; char ch=getchar(); for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1; for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0'; return x*f; } long long a,b,x,y,d,t; inline void exgcd(long long a,long long b,long long &d,long long &x,long long &y){ if(!b) d=a,x=1,y=0; else exgcd(b,a%b,d,x,y),t=x,x=y,y=t-a/b*y; } int main(){ in(a),in(b); exgcd(a,b,d,x,y); long long a1=a/d,b1=b/d; printf("%lld",(x
