洛谷P1082 [NOIP2012 提高组] 同余方程

 

 这题不能用费马小定理，b不一定是质数，求逆元是能满足互质条件，但是费马小定理还需要b是质数；

 

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 ll exgcd(ll &x,ll &y,ll a,ll b)
 5 {
 6     if(!b)
 7     {
 8         x=1,y=0;
 9         return a;
10     }
11     ll p=exgcd(x,y,b,a%b);
12     ll xx=x,yy=y;
13     x=yy;
14     y=xx-(a/b)*yy;
15     return p;
16 }
17 int main()
18 {
19     ll a,b,x=0,y=0;
20     cin>>a>>b;
21     exgcd(x,y,a,b);
22     cout<<(x+b)%b<<endl;//求出来的不一定是最小正整数解，避免出现负值； 
23     return 0;
24  }