luogu1082 [NOIp2012]同余方程 (扩展欧几里得)

 1 #include<bits/stdc++.h>
 2 #define pa pair<int,int>
 3 #define CLR(a,x) memset(a,x,sizeof(a))
 4 using namespace std;
 5 typedef long long ll;
 6 const int maxn=1;
 7 
 8 inline ll rd(){
 9     ll x=0;char c=getchar();ll neg=1;
10     while(c<‘0‘||c>‘9‘){if(c==‘-‘) neg=-1;c=getchar();}
11     while(c>=‘0‘&&c<=‘9‘) x=x*10+c-‘0‘,c=getchar();
12     return x*neg;
13 }
14 
15 void exgcd(ll a,ll b,ll &x,ll &y){
16     if(b==0){x=1,y=0;return;}
17     ll x1,y1;
18     exgcd(b,a%b,x1,y1);
19     x=y1;y=x1-a/b*y1;
20 }
21 
22 int main(){
23     ll a=rd(),b=rd();ll x,y;
24     exgcd(a,b,x,y);
25     printf("%lld\n",(x%b+b)%b);
26     return 0;
27 }