标签归档:数论

[zoj4056][ICPC 2018 Qingdao Online]Press the Button

Link

Solution

问题最后是求一个长度为$t$的数轴上有多少对相邻的关键点距离$\ge v$,关键点是所有$a$和$c$的倍数的点。
假设$a < c$
如果$a < v$则不存在
否则
考虑$c$的倍数与它后面相邻的$a$的倍数的距离
根据根据鸽巢原理,至多$c$步,这个距离就会开始循环
然后把$t$分成三部分:
不在循环+循环部分+一段没循环完的部分
细节巨多写到脑壳疼
~正解是模拟到${\rm lcm}(a,b)$,直接判断,然后循环~

Code

const int XN=1e6+11;
void Work() {
    long long v,t,a,b,c,d;
    fin>>a>>b>>c>>d>>v>>t;
    long long Ans=(long long)((t/a)+1)*b+(long long)((t/c)+1)*d-1;
    if(a>v && c>v) {
        if(a>c)
            std::swap(a,c);
        static int us[XN],ut;
        static long long crec[XN],prec[XN];
        ++ut;long long cnt=0,pc=0,py=0;
        for(;;pc+=c) {
            long long x=(pc/a)*a,y=x+a; 
            cnt+=((pc-x)>v)+((y-pc)>v)+(x-py)/a;
            py=y;
            if(us[y-pc]==ut)
                break;
            us[y-pc]=ut;
            crec[y-pc]=cnt;
            prec[y-pc]=py;
        }
        if(t>prec[py-pc]) {
            long long circnt=cnt-crec[py-pc],cirlen=py-prec[py-pc];
            Ans-=circnt*((t-prec[py-pc])/cirlen)+crec[py-pc];
            py+=((t-prec[py-pc])/cirlen-1)*cirlen;
            pc=(py/c+1)*c;
        } else {
            py=pc=0;
        }
        if(pc<=t)
            for(;;pc+=c) {
                long long x=(pc/a)*a,y=x+a;
                Ans-=((pc-x)>v)+(x-py)/a;
                if(y<=t) {
                    Ans-=((y-pc)>v);
                }
                py=y;
                if(pc+c>t)
                    break;
            }
        if(py<t)
            Ans-=(t-py)/a;
    }
    fout<<Ans<<'\n';
}

int main() {
    int T;fin>>T;
    while(T--)
        Work();
    return 0;
}