P1516 青蛙的约会(exgcd以及相关结论)

非常好的题，适合入门拓展欧几里得算法以及相关结论。

结论

ax + by = gcd(a,b) = gcd(b,a%b) = $bx + (a - \left \lfloor \frac{a}{b} \right \rfloor \times b) y = ay + b(x-\left \lfloor \frac{a}{b} \right \rfloor )$

由此递归求解即可。

int exgcd(int a,int b,int &x,int &y){//	求解 ax + by = gcd(a,b)if(!b){x = 1,y = 0;return a;}int g = exgcd(b,a%b,x,y);int temp = x;x = y;y = temp-a/b*y;return g;
}

求解ax + by = c 的特解

先求解 gcd(a,b) 若 c/gcd(a,b) 不是整数则说明无解。

证明：因为 (ax + by)/g 一定是整数所以 c/gcd(a,b) 也要是整数。

易证：求出 ak+bl = gcd(a,b)后，令w = c/gcd(a,b),x = w*k,y = w*l。

bool liEu(int a,int b,int &x,int &y,int c){//求解ax + by = cint g = exgcd(a,b,x,y);if(c % g != 0)return 0;//无解int k = c/g;x*=k;y*=k;return 1;
}

最小非负整数解

有恒等式 a(x0 + k*d*b ) + b(y0 - k*d*a)。

x = x0 + db,最小的划分度，为d = 1/gcd(a,b)。

令 t = b/gcd(a,b);

则x最小值 = x0 - k*t > 0 满足取模的定义，故 min = x0 mod t，为了防一手x0是负数，所以

最小值是（x0 mod t + t) mod t

解题思路

(m-n)x + la = x-y (mod l)

a = (m-n)

b = l

c = x-y

细节：防一手m - n < 0 则令 a = -a ,c = -c。b不用管，由整除性可得。

。故求解ax + by = c中x的最小整除解即可。

AC 代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y){//	求解 ax + by = gcd(a,b)if(!b){x = 1,y = 0;return a;}int g = exgcd(b,a%b,x,y);int temp = x;x = y;y = temp-a/b*y;return g;
}
bool liEu(int a,int b,int &x,int &y,int c){//求解ax + by = cint g = exgcd(a,b,x,y);if(c % g != 0)return 0;//无解int k = c/g;x*=k;y*=k;return 1;
}
signed main(){int x,y,n,m,l;cin>>x>>y>>m>>n>>l;int a = n-m;int b = l;int xx,yy;int c = x-y;if(a < 0){c = -c,a = -a;}if(liEu(a,b,xx,yy,c)){int t = b/__gcd(a,b);cout<<(xx%t + t)%t;}else{puts("Impossible");	}return 0;
}