转洛谷P1208同余方程  -> (https://www.luogu.org/problemnew/show/P1082)

---

 

这就是一个有一点小弯的扩展欧几里得的模板题
根据 ax ≡ 1( mod b) 这个方程你应该化简成ax - by

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long int
 4 ll exgcd(ll m, ll n, ll & x, ll & y)
 5 {
 6     if(n==0)
 7     {
 8         x=1;
 9         y=0;
10         return m;
11     }
12     else
13     {
14         ll r=exgcd(n,m%n,x,y);
15         ll temp=y;
16         y=x-(m/n)*y;
17         x=temp;
18         return r;
19     }
20 }
21 int main()
22 {
23     ll a,b,c,d,e,f;
24     ll x,y;
25     cin>>a>>b;
26     c=exgcd(a,b,x,y); 
27    /// 这里求得c是最大公约数，因为刚刚给的方程ax - by = 1 如果存在x、y的值的话c就一定是互质的
28    /// 这里题目给的是一定存在，所以c的值就一定为1。所以这里看你们心情加就行了。
29     if(c==1)
30     {
31         if(x<0)
32         while(x<0)
33             x+=abs(b);
34         else
35         {
36             while(x>0)
37                 x-=abs(b);
38             x+=abs(b);
39         }
40         cout<<x<<endl;
41     }
42     return 0;
43 }

注意：：

因为最后题目要求是求出x的最小的非零值，所以我们有这么个结论：
ax+by=1
a x + b y + k × b a − k × b a = 1
a ( x + k b ) + ( y − k a) b = 1
所以我们知道在x的后面加上k倍的b和y的后面同时减去k倍的a这个等式依旧成立，
所以根据这对结果进行简单处理一下就成了。