ABC193E
dyj133446
2022-12-07 12:14:57
### 题目大意
[题目传送门](https://www.luogu.com.cn/problem/AT_abc193_e)
多组数据。一个人坐公交从 $A$ 站坐到 $B$ 站，公交车先用 $x$ 秒到 $B$ 站，然后在 $B$ 站停 $y$ 秒，再用 $x$ 秒到 $A$ 站，再在 $A$ 站停 $y$ 秒，如此循环往复。而这个人先睡眠 $p$ 秒，再醒来 $q$ 秒，如此循环往复。求这个人最早何时能在 $B$ 站下车，若永远不能，输出 $infinity$。
### 题目分析
令公交车往返两地 $a$ 次，此人已循环过程 $b$ 次，公交车停在 $B$ 地 $m$ 秒，此人醒来 $n$ 秒下车，可得等式：
$2a(x+y)+x+m=b(p+q)+p+n$
经整理得：
$2a(x+y)+(-b)(p+q)=(p+n)-(x+m)$
于是我们想到**扩欧**。
先解方程 $2a(x+y)+(-b)(p+q)=\gcd(2(x+y),p+q)$
令 $i=x+m,j=p+n$
枚举 $i,j$，求出 $a$ 的最小正整数解，代入第一个式子求解，取最小值输出，时间复杂度 $O(yq+\log(\max(2(x+y),p+q))$。
### AC代码
```cpp
#include<bits/stdc++.h>
using namespace std;
bool flag;
long long t,x,y,p,q,d,a,b,minn=0x7fffffffffffffff;
long long ans;
void Exgcd(long long a,long long b,long long &x,long long &y)
{
if(!b)
{
d=a,x=1,y=0;
return;
}
Exgcd(b,a%b,x,y);
long long tx=x;
x=y;
y=tx-a/b*y;
}
int main()
{
cin>>t;
for(int t1=1;t1<=t;t1++)
{
cin>>x>>y>>p>>q;
minn=0x7fffffffffffffff;
flag=0;
Exgcd(2*(x+y),p+q,a,b);
for(long long i=x;i<x+y;i++)
{
for(long long j=p;j<p+q;j++)
{
if((j-i)%d!=0)continue;
flag=1;
long long k=(j-i)/d;
long long aa=a*k;
aa=(aa%((p+q)/d)+((p+q)/d))%((p+q)/d);
minn=min(minn,aa*2*(x+y)+i);
}
}
if(!flag)cout<<"infinity";
else cout<<minn;
cout<<'\n';
}
return 0;
}
```
## 别慌，还有优化
我们可以直接枚举 $j-i$,算出最小的 $i$ 代入求最小值，时间复杂度 $O(y+q+\log(\max(2*(x+y),p+q))$。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
bool flag;
long long t,x,p,d,a,b,minn=0x7fffffffffffffff;
int y,q;
long long ans;
void Exgcd(long long a,long long b,long long &x,long long &y)
{
if(!b)
{
d=a,x=1,y=0;
return;
}
Exgcd(b,a%b,x,y);
long long tx=x;
x=y;
y=tx-a/b*y;
}
int main()
{
cin>>t;
for(int t1=1;t1<=t;t1++)
{
cin>>x>>y>>p>>q;
minn=0x7fffffffffffffff;
flag=0;
Exgcd(2*(x+y),p+q,a,b);
for(long long i=p-(x+y-1);i<=p+q-1-x;i++)
{
if(i%d!=0)continue;
flag=1;
long long k=i/d;
long long aa=a*k;
aa=(aa%((p+q)/d)+((p+q)/d))%((p+q)/d);
if(i>=p-x)minn=min(minn,aa*2*(x+y)+x);
else minn=min(minn,aa*2*(x+y)+x+(p-x-i));
}
if(!flag)cout<<"infinity";
else cout<<minn;
cout<<'\n';
}
return 0;
}
```