BZOJ-3834: [Poi2014]Solar Panels

Description

n组询问，每次问smin<=x<=smax, wmin<=y<=wmax时gcd(x, y)的最大值。1<=N<=1000 ；1<=Smin<=Smax<=10^9,1<=Wmin<=Wmax<=10^9。

假设答案为ans，那么则有
分块找合法最大的ans。理论上取下整也可行，但是取上整遇到解直接跳出会很快。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
inline int cie(int x,int y)
{
    return x%y?x/y+1:x/y;
}
int main()
{
    int t,l1,l2,r1,r2,b,e,ans;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        r1++; r2++; ans=1; b=min(r1,r2);
        e=max( max(cie(r1,cie(r1,b)) , cie(l1,cie(l1,b)) ) , max(cie(r2,cie(r2,b)) , cie(l2,cie(l2,b)) ) );
        while(b>=1)
        {
            if(cie(r1,b)>cie(l1,b)&&cie(r2,b)>cie(l2,b))
            {
                ans=b;
                break;
            }
            b=e-1;
            e=max( max(cie(r1,cie(r1,b)) , cie(l1,cie(l1,b)) ) , max(cie(r2,cie(r2,b)) , cie(l2,cie(l2,b)) ) );
        }
        printf("%d\n",ans);
    }
    return 0;
}