题解 P1516 【青蛙的约会】
P1516 青蛙的约会
题目大意：
有一个长度为 \(l\) 的圆环，圆环上有两个点 \(A,B\) ，分别位于 \(x,y\) ，每次分别可跳 \(m,n\) 个单位，问跳多少次相遇。无解输出 Impossible 。
solution：
对此可列出同余方程：
\[(x+am)\equiv (y+an)(\bmod l) \]展开：
\[(x+am)-(y+an)=bl \]\[x-y+a(m-n)=bl \]\[a(m-n)-bl=y-x \]这里 \(a,b\) 即为我们所求。扩欧后推广解就行了。但由于 \(x=x_0+ k\frac{b}{\gcd(a,b)}\) ，所以求最小正整数要对 \(\frac{b}{\gcd(a,b)}\) 取模。
细节处理：
- 开LL。
- 注意无解情况。
代码
#include
using namespace std;
typedef long long LL;
LL xx,yy;
inline int exgcd(int a,int b){
if(!b){
xx=1,yy=0;
return a;
}
int d=exgcd(b,a%b);
LL tx=xx;
xx=yy,yy=tx-a/b*yy;
return d;
}
int main(){
int x,y,m,n,l;
scanf("%d%d%d%d%d",&x,&y,&m,&n,&l);
int n_m=(n%l-m%l+(LL)l)%l,x_y=(x%l-y%l+(LL)l)%l;//处理下负数
int d=exgcd(n_m,l);
if(x_y%d!=0) return puts("Impossible"),0;//特判无解
xx=(x_y/d*xx%(l/d)+(l/d))%(l/d);//推广
printf("%lld",xx);
return 0;
}