orz jason_yu提醒了我一句“最简单的优化”,才想起来。


如果d合法的话那么b/d-(a-1)/d>0。然后用整除优化到sqrt就可过。虽然比较慢。


#include <cstdio>

#include <cstring>

#include <algorithm>


using namespace std;


int main() {

int t, a, b, c, d, s, e;

scanf("%d", &t);

while (t --) {

scanf("%d%d%d%d", &a, &b, &c, &d);

-- a;

-- c;

s = 1;

e = min(b, d);

for (int i = 1, j; i <= e; i = j + 1) {

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

if (a / i)

j = min(j, a / (a / i));

if (c / i)

j = min(j, c / (c / i));

if (a / i < b / i && c / i < d / i)

s = j;

}

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

}

}