CF346E-Doodle Jump【類歐】

正題

題目連結:https://www.luogu.com.cn/problem/CF346E

題目大意

給出\(a,n,p,h\)，在每個\(ax\%p(x\in[0,n])\)的位置有一個關鍵點，詢問是否所有相鄰關鍵點之間的距離都不超過\(h\)。

解題思路

沒怎麼寫過類歐，這個題還是很坑的，需要考慮求一下\(h\)需要的最小值（相鄰關鍵點直接距離的最大值）

首先第一個循環肯定都是\(ax\)的位置有關鍵點了，然後第二個循環開始是\(\lceil\frac{p}{a}\rceil a-p+ax\)，然後每個循環的起點加一個\(\lceil\frac{p}{a}\rceil a-p\)。好像就可以用類歐把一個大問題縮減成一個小問題了。

考慮一下細節，首先是末尾那一段，也就是\(a\lfloor\frac{p}{a}\rfloor+1\sim p\)這一段是沒有用的，因為如果這一段無法到達最末尾處，那麼一定存在某個\(k\)使得\(ka\)無法到達\((k+1)a\)。

然後考慮有多少個可行的循環，簡單的看是\(\lfloor\frac{an}{p}\rfloor\)，但是這樣可能會有某些周期沒有跑完的情況，那麼後面那些間隔是沒有變小的，考慮到我們求的是最大間隔，肯定是取後面的，是以此時要減一。

然後當\(an\leq p\)的時候就可以取答案了。

時間複雜度\(O(\log n)\)

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
ll a,n,p,h,T;
ll solve(ll a,ll n,ll p){
    if(a*n<p)return max(a,p-a*n);
    ll z=a*n/p;
    if(a*n%p<p/a*a-a)z--;
    return solve((p+a-1)/a*a-p,z,a);
}
signed main()
{
    scanf("%lld",&T);
    while(T--){
        scanf("%lld%lld%lld%lld",&a,&n,&p,&h);
        a%=p;
        if(a<=h){puts("YES");continue;}
        if(a*n<=p){puts(h>=a?"YES":"NO");continue;}
        puts((solve(a,n,p)<=h)?"YES":"NO");
    }
    return 0;
}