[POI2014] PAN-Solar Panels

标签：lfloor right last int POI2014 rfloor Solar PAN left

区间 \(\left( l,r \right]\) 中存在 \(n\) 的倍数的充要条件是 \(\left\lfloor \frac{r}{n}\right\rfloor > \left\lfloor \frac{l}{n}\right\rfloor\)。

证明：记有整数 \(k\) 满足 \(k \times n \in \left( l,r \right]\)。

那么有

\[\displaystyle l < k \times n \leqslant r \Longleftrightarrow \dfrac{l}{n} < k \leqslant \dfrac{r}{n} \Longleftrightarrow \left\lfloor \frac{l}{n}\right\rfloor < \left\lfloor \frac{r}{n}\right\rfloor \]

证毕。

记 \(\gcd(x,y)=k\)，我们可以枚举 \(k\)，因为 \(a \leqslant x \leqslant b\)，所以我们可以枚举 \(k\)。

但暴力枚举 \(k\) 肯定是会超时，那我们就用整除分块优化。

没学过整除分块可以看这个。

Code

#include <bits/stdc++.h>

using namespace std;

int n;
int a,b,c,d;
int last,ans;

int main() {
#ifdef ONLINE_JUDGE == 1
    freopen("melina.in","r",stdin);
    freopen("melina.out","w",stdout);
#endif
    cin >> n;
    for(int t = 1;t <= n; t++) {
        cin >> a >> b >> c >> d;

        for(int i = 1;i <= b && i <= d; i = last + 1) {
            last = min(d / (d / i),b / (b / i));
            // 整除分块的右端点，实际是范围内的最大值 
            if(b / last > (a - 1) / last && d / last > (c - 1) / last)
                ans = last;// 利用性质 
        }

        cout << ans << "\n";
    }
#ifdef ONLINE_JUDGE == 1
    fclose(stdin);
    fclose(stdout);
#endif
    return 0;
}

标签：lfloor,right,last,int,POI2014,rfloor,Solar,PAN,left
From： https://www.cnblogs.com/baijian0212/p/solution-p3579.html