[文章目录]
Description
张骞所处的经度为x，康破伦所处的经度为y；接下来，两人同时向西走，而且只能向西走，张骞每天走m公里，康破伦每天走n公里，且每天走路的速度不变，也不停下来休息；这样两人就在这一条长为L的纬度线上一直向西走。问：过了多少天之后张骞和康破伦会碰面，并磋商两国结交之事（所谓碰面，是指两人处在同一经度上）。(输入只包括一行5个整数x，y，m，n，L 其中0< x≠y < =2000000000，0 < m、n < =2000000000，0 < L < =2100000000。)
woc首先，这是瞬移就够恶心的了，还。。。开LL。然后，不知道为啥，还就是莫名WA o_0。
结果是最后Mod的数整错了，应该是b/gcd(a,b);
我好菜啊。。。
#include <iostream>
#include <cstdio>
#include <algorithm>
#define LL long long
using namespace std;
LL x,y,m,n,l,a,b,c,t;
LL gcd(LL a,LL b)
{return !b ? a:gcd(b,a%b);}
void extgcd(LL a,LL b,LL &x,LL &y)
{
if(b==0){x=1;y=0;return;}
exgcd(b,a%b,x,y);
LL t=x;x=y;y=t-a/b*y;
}
int main()
{
scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
if(n<m)
{
swap(n,m);
swap(x,y);
}
a=n-m;b=l;c=x-y;
t=gcd(a,b);
if(c%t!=0){printf("Impossible\n");return 0;}//ax+by=c有解的充分必要条件是gcd(a,b)|c(c能整除gcd(a,b);).
a/=t;b/=t;c/=t;
extgcd(a,b,x,y);
x=((c*x)%b+b)%b;//注意mod的是b/gcd(a,b);证明见后
printf("%lld\n",x);
return 0;
}证明：
ax+by=gcd(a,b);的特解是k ax*c+by*c=gcd(a,b)*c; a(x*c)/gcd(a,b)+b(y*c)/gcd(a,b)=c; 设x*c/gcd(a,b)=p; 那么，p每次可降低的值（设为q）就是使a*q能整除b的min； 然后因为a=gcd(a,b)*k,所以说，q最小必须含有一个约数b/gcd(a,b); 所以p最后mod的是b/gcd(a,b);