将初中wyz讲的数论整理一下（感谢我的笔记本还活着 卷子全扔了QAQ）
拓展欧几里德模版 来源：百度百科
1 int exgcd(int a,int b,int &x,int &y) 2 { 3 if(!b) {x=1,y=0;return a;} 4 int r=exgcd(b,a%b,x,y); 5 int t=x;x=y,y=t-a/b*y; 6 return r; 7 }
证明先咕了QAQ
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 ll a,b,x,y; 5 6 template<class t>void rd(t &x) 7 { 8 x=0;int w=0;char ch=0; 9 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 10 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 11 x=w?-x:x; 12 } 13 14 ll exgcd(ll a,ll b,ll &x,ll &y) 15 { 16 if(!b) {x=1,y=0;return a;} 17 ll r=exgcd(b,a%b,x,y); 18 ll t=x;x=y,y=t-a/b*y; 19 return r; 20 } 21 22 int main() 23 { 24 rd(a),rd(b); 25 exgcd(a,b,x,y); 26 printf("%lld",(x%b+b)%b); 27 return 0; 28 }