题目：
模拟法思路：
首先考虑不会相遇的情况，是坐标出现重复的情况。（和紫书巨大的斐波那切数列差不多）。
模拟法先试试：
代码应该没问题，但是显然会超时。
a
= input()
aa
= a
.split
()
x1
= int(aa
[0])
x2
= int(aa
[1])
v1
= int(aa
[2])
v2
= int(aa
[3])
ll
= int(aa
[4])
ll2
= [[]for i
in range(0)]
ok
= 0
while 1:
l1
= []
l1
.append
(x1
)
l1
.append
(x2
)
if l1
in ll2
:
ok
= 0
break
ll2
.append
(l1
)
ok
= ok
+1
x1
= (x1
+ v1
) % ll
x2
= (x2
+ v2
) % ll
if x1
== x2
:
break
if ok
== 0:
print("Impossible")
else:
print(ok
)
数学法分析：
能够相遇： x1+v1t = x2+v2t + N*ll t存在大于0的整数解即可。 （v2-v1)t+Nll=x1-x2
还是t>0就可以把。
gcd只对非负整数有意义。
代码：
#include<bits/stdc++.h>
using namespace std
;
int gcd1(int a
,int b
)
{
return b
==0?a
:gcd1(a
,a
%b
);
}
void gcd2(int a
,int b
,int& d
,int& x
,int& y
)
{
if(!b
){
d
=a
;x
=1;y
=0;
}
else{
gcd2(b
,a
%b
,d
,y
,x
);y
-=x
*(a
/b
);
}
}
int main()
{
int x
,y
,m
,n
,l
;
cin
>>x
>>y
>>m
>>n
>>l
;
int a
=m
-n
;
int b
=l
;
int c
=y
-x
;
if(a
<0)
{
a
=-a
;
b
=max(b
,-b
);
c
=-c
;
}
else {
b
=max(b
,-b
);
}
int gcd
=gcd1(a
,b
);
int x1
,y1
;
gcd2(a
,b
,gcd
,x1
,y1
);
c
=(c
-c
/l
*l
+l
)%l
;
if(c
%gcd
) cout
<<"Impossible";
else{
int t
=b
/gcd
;
cout
<<((long long)x1
*c
/gcd
-(long long)x1
*c
/gcd
/t
*t
+t
)%t
;
}
}
详细标注：
#include<bits/stdc++.h>
using namespace std
;
int gcd1(int a
,int b
)
{
return b
==0?a
:gcd1(a
,a
%b
);
}
void gcd2(int a
,int b
,int& d
,int& x
,int& y
)
{
if(!b
){
d
=a
;x
=1;y
=0;
}
else{
gcd2(b
,a
%b
,d
,y
,x
);y
-=x
*(a
/b
);
}
}
int main()
{
int x
,y
,m
,n
,l
;
cin
>>x
>>y
>>m
>>n
>>l
;
int a
=m
-n
;
int b
=l
;
int c
=y
-x
;
if(a
<0)
{
a
=-a
;
b
=max(b
,-b
);
c
=-c
;
}
else {
b
=max(b
,-b
);
}
int gcd
=gcd1(a
,b
);
int x1
,y1
;
gcd2(a
,b
,gcd
,x1
,y1
);
c
=(c
-c
/l
*l
+l
)%l
;
if(c
%gcd
) cout
<<"Impossible";
else{
int t
=b
/gcd
;
cout
<<((long long)x1
*c
/gcd
-(long long)x1
*c
/gcd
/t
*t
+t
)%t
;
}
}
