ABC193E

dyj133446 · 2022-12-07 12:14:57 · 题解

题目大意

题目传送门
多组数据。一个人坐公交从 A 站坐到 B 站，公交车先用 x 秒到 B 站，然后在 B 站停 y 秒，再用 x 秒到 A 站，再在 A 站停 y 秒，如此循环往复。而这个人先睡眠 p 秒，再醒来 q 秒，如此循环往复。求这个人最早何时能在 B 站下车，若永远不能，输出 infinity。

题目分析

令公交车往返两地 a 次，此人已循环过程 b 次，公交车停在 B 地 m 秒，此人醒来 n 秒下车，可得等式：

经整理得：

于是我们想到扩欧。
先解方程 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代码

#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))。
代码：

#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;
}