[比赛][暴力][循环][复杂度分析] 2018 icpc 青岛网络赛 J Press the Button

还好没有鸽这场比赛，当时是做数模的最后几小时，我和lyq没办法只能让iSika单挑，期间顶着40小时没休息的脑袋帮他过了一个水题和一个计数递推形的dp，然后看看J过的人挺多，准备去看却发现脑子实在太疼根本读不完题，然后iSika说他大概能过那个B，然后我就不管了去瞎编数模论文。。。

没想到的是晚上肝完数模去打印论文的时候，掏出手机发现代哥给我发消息问去沈阳赛区不去。。当时其实本来已经累得要死了但是看到这个瞬间高潮了，简直哭了，真的好不容易得到的icpc现场赛机会。。。

然后我在队里小群兴高采烈地发消息结果半天没人回我，嗯友尽系列（都在睡觉吗朋友们？？

然后后来一直在忙微软俱乐部的面试，到现在在高铁上才有空去看这几场区域赛攒的题，先把这个J补了，当时以为复杂度不可取，实际上就是一lcm循环，而lcm里a或c的倍数的数量最多1e6，所以不会超时。需要分成三段处理，第一段是[0,lcm)，第二段是[lcm,k*lcm)，第三段是[k*lcm,t]，其中第二段的计算只需要算(k-1)*[lcm,2*lcm)就可以了，也就是说三段复杂度都是1e6。当然有几段还得根据t与lcm的相对大小来具体判断。之所以第一段和中间循环段分别考虑，就是因为一开始的条件是灯都是灭的，但是在第一个lcm循环结束之后灯光却有可能是亮的，所以需要特别考虑这种情况。最后把三段的答案加起来就得到了最后的答案。

#include 
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=1e6+5;

LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}

LL lcm(LL a,LL b)
{
    return a/gcd(a,b)*b;
}

int cnt;
LL ar[maxn<<2];

int main()
{
    int T,tp;
    LL a,b,c,d,v,t,lc,maxr,lp1,lp2,ps,res,ans,flag=0;
    scanf("%d",&T);
    while(T--)
    {
        flag=0;
        lp1=lp2=res=ps=ans=cnt=0;
        scanf("%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&v,&t);
        lc=lcm(a,c);
        for (int k=0; k*a<=lc; k++)
            ar[++cnt]=k*a;
        for (int k=0; k*c<=lc; k++)
            ar[++cnt]=k*c;
        sort(ar+1,ar+1+cnt);
        tp=cnt;
        cnt=1;
        for (int i=2; i<=tp; i++)
        {
            if(ar[i]!=ar[cnt])
                ar[++cnt]=ar[i];
        }
        
        maxr=-1;
        if(ar[cnt]-1<=t)
        {
            lp1=0;
            maxr=-1;
            for (int i=1; imaxr)
                    lp1--;
                if(ar[i]%a==0)
                    lp1+=b;
                if(ar[i]%c==0)
                    lp1+=d;

                maxr=v+ar[i];
                
            }
        }
        
        if(ar[cnt]<=maxr)
            flag=1;
        if(2*ar[cnt]-1<=t&&ar[cnt]<=maxr)
        {
            lp2=maxr=0;
            for (int i=1; imaxr)
                    lp2--;
                if(ar[i]%a==0)
                    lp2+=b;
                if(ar[i]%c==0)
                    lp2+=d;
                maxr=v+ar[i];

            }
        }
        else if(2*ar[cnt]-1<=t)
            lp2=lp1;
        else
            lp2=0;

        

        if(ar[cnt]-1<=t)
            ps=(t+1)/ar[cnt];
        else
            ps=0;

        res=t+1-ps*(ar[cnt]);
        
        if(res)
        {
            res--;
            if(!flag)
                maxr=-1;
            else
                maxr=t+1;
            for (int i=1; imaxr)
                    ans--;
                if(ar[i]%a==0)
                    ans+=b;
                if(ar[i]%c==0)
                    ans+=d;

                maxr=ar[i]+v;
           
            }
        }
        
        ans+=lp1+(ps-1)*lp2;
        cout<