Luogu3579 Solar Panels

整除分块枚举。。。

真的没有想到会这么简单。

要使一个数 \(p\) 满足条件，则存在\(x, y\)， \(a<=x \times p<=b\ \&\&\ c<=y \times p <=d\)

把\(p\) 除掉则

　　 \(\left\lceil\dfrac{a}{p}\right\rceil <=y <=\left\lfloor\dfrac{b}{p}\right\rfloor\)

　　 \(\left\lceil\dfrac{c}{p}\right\rceil <=y <=\left\lfloor\dfrac{d}{p}\right\rfloor\)

把向上取整变为向下取整

　　 \(\left\lfloor\dfrac{a+p-1}{p}\right\rfloor <= \left\lfloor\dfrac{b}{p}\right\rfloor\)

　　 \(\left\lfloor\dfrac{b+p-1}{p}\right\rfloor <= \left\lfloor\dfrac{d}{p}\right\rfloor\)

然后就变成了：

　　\(\left\lfloor\dfrac{a-1}{p}\right\rfloor < \left\lfloor\dfrac{b}{p}\right\rfloor\)

　　\(\left\lfloor\dfrac{b-1}{p}\right\rfloor < \left\lfloor\dfrac{d}{p}\right\rfloor\)

最后整除分块。只需按照 \(b/p\)和\(d/p\) 相同时进行分类。这样能使 \(b/p\) 和 \(d/p\)相等的同时 \(c/p\) 和 \(d/p\)尽量小，更可能满足条件

#include<cstdio>

#include<cstring>

#include<algorithm>

#define rd read()

#define R register

using namespace std;

inline int read() {

    int X = 0, p = 1; char c = getchar();

    for (; c > '9' || c < '0'; c =  getchar())

        if (c == '-') p = -1;

    for (; c >= '0' && c <= '9'; c = getchar())

        X = X * 10 + c - '0';

    return X * p;

}

inline void cmax(int &A, int B) {

    if (A < B) A = B;

}

inline int cmin(int A, int B) {

    return A > B ? B : A;

}

void work() {

    int ans = 1;

    int a = rd - 1, b = rd, c = rd - 1, d = rd;

    for (R int i = 1, j = 1, up = cmin(b, d); i <= up; i = j + 1) {

        j = cmin(b / (b / i), d / (d / i));

        if (b / j > a / j && d / j > c / j) cmax(ans, j);

    }

    printf("%d\n", ans);

}

int main()

{

    int n = rd;

    for (; n; --n) work();

}

巴特西

Luogu3579 Solar Panels

最新文章

热门文章