AdditionalFile4932.zip

P3579 [POI 2014] PAN-Solar Panels

题目描述

对于 $n$ 组询问，每组询问给定四个整数 $a,b,c,d$，从区间 $[a,b]$ 和 $[c,d]$ 中任意选取两个整数 $x$ 和 $y$，求 $\gcd(x,y)$ 的最大值是多少。

输入格式

第一行一个整数 $n$ 代表询问数。
接下来 $n$ 行每行代表一个询问，四个整数 $a,b,c,d$ 代表两个区间的范围。

输出格式

$n$ 行每行一个整数代表区间 $[a,b]$ 和 $[c,d]$ 中任意选取两个整数 $x$ 和 $y$，$\gcd(x,y)$ 的最大值。

输入输出样例 #1

输入 #1

4
3 9 8 8
1 10 11 15
4 7 22 23
2 5 19 24

输出 #1

8
7
2
5

说明/提示

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le a \le b \le 10^9$，$1 \le c\le d \le 10^9$。

说明

Translated by @一只书虫仔。

#4932. 「POI2014 R3」太阳能板 Solar Panels

标签: 传统 | 时间限制: 10000 ms | 内存限制: 128 MiB |

题目描述

题目译自 XXI Olimpiada Informatyczna — III etap Panele słoneczne

Bajtazar 投身绿色能源，创办了一家太阳能板工厂，生意火爆！短短几天，就有 $n$ 位客户下单，每人订购一块矩形太阳能板，并指定了宽高范围。

太阳能板由正方形光伏电池组成，电池边长可为任意整数，但同一块板的所有电池必须大小相同。生产工艺决定了电池越大，板子效率越高。Bajtazar 希望为每块订购的板子确定可用的最大电池边长。请你帮他计算！

输入格式

输入第一行包含一个整数 $n$ $(1 \leq n \leq 1000)$，表示订购的太阳能板数量。

接下来的 $n$ 行描述各块板子，第 $i$ 行包含四个整数 $s_{\min}, s_{\max}, w_{\min}, w_{\max}$ $(1 \leq s_{\min} \leq s_{\max} \leq 10^9, 1 \leq w_{\min} \leq w_{\max} \leq 10^9)$，分别表示第 $i$ 块板子的最小和最大宽度、最小和最大高度。

输出格式

输出 $n$ 行，第 $i$ 行一个整数，表示可用于第 $i$ 块太阳能板的最大电池边长。

样例

输入

4
3 9 8 8
1 10 11 15
4 7 22 23
2 5 19 24

输出

8
7
2
5

Bajtazar 将生产四块太阳能板，尺寸分别为：$8 \times 8$（由 $1$ 个电池组成）、$7 \times 14$（由 $2$ 个电池组成）、$4 \times 22$ 或 $6 \times 22$（由 $22$ 或 $33$ 个电池组成）、$5 \times 20$（由 $4$ 个电池组成）。

附加样例

1. $n=1000, s_{\max}, w_{\max} \leq 10^7$，每块板子的最大电池边长等于 $s_{\max}$。

数据范围与提示

对于 $20\%$ 的数据，$n \leq 10$。 对于 $75\%$ 的数据，$s_{\max}, w_{\max} \leq 10^7$。