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

 这题费马小定理肯定不行，费马小定理的前提是p为质数，gcd(a,p)=1，即互质；所以我们只能考虑拓展欧几里得

 1 #include
 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<//求出来的不一定是最小正整数解，避免出现负值； 
23     return 0;
24  }