AdditionalFile4834.zip

P9401 [POI 2020/2021 R3] 收藏家 2 / Kolekcjoner Bajtemonów 2

题目背景

译自 XXVIII Olimpiada Informatyczna - III etap Kolekcjoner Bajtemonów 2。

试机题。

题目描述

给你 $n$ 个数对，你要进行 $n$ 次二选一，这样你就有了 $n$ 个数，最大化这 $n$ 个数的 $\gcd$。

输入格式

第一行一个正整数 $n$。

接下来 $n$ 行，每行两个整数，$a_i,b_i$。

输出格式

一行一个数：最大的 $\gcd$。

输入输出样例 #1

输入 #1

4
5 7
10 15
13 20
7 5

输出 #1

5

输入输出样例 #2

输入 #2

2
18900 22050
14700 17640

输出 #2

7350

输入输出样例 #3

输入 #3

见附件

输出 #3

2

说明/提示

对于所有数据，$1\leq n\leq 10^6$，$1\leq a_i\leq 5\times 10^5$，$1\leq b_i<2^{63}$。

对于 $42pts$ 的数据，$n\leq 5000$。

#4834. 「POI 2020/2021 R3」Kolekcjoner Bajtemonów 2

标签: 传统 | 时间限制: 4000 ms | 内存限制: 256 MiB |

题目描述

题目译自 XXVIII Olimpiada Informatyczna – III etap Kolekcjoner Bajtemonów 2

Bajtazar 拥有一套数量庞大的 Bajtemon 卡牌收藏。在他的卡牌堆中，每张卡牌上都画着一只 Bajtemon，并标注了它进化前和进化后的战斗力。Bajtazar 决定卖掉这套收藏。根据《字节-比特卡牌交易协议》，收藏的总价值与卡牌堆中所有 Bajtemon 战斗力的最大公约数成正比。然而，这份协议并未考虑到一张卡牌可能标注多个战斗力的情况，因此 Bajtazar 可以自由选择每张卡牌是使用进化前的战斗力，还是进化后的战斗力。

当然，他希望通过选择使最终的最大公约数尽可能大，从而卖出最高的价格。请你写一个程序，帮助他计算出能卖出的最高价值。

输入格式

输入的第一行包含一个整数 $n$ $(1 \leq n \leq 10^{6})$，表示 Bajtazar 卡牌堆中的卡牌数量。接下来的 $n$ 行描述每张卡牌上的 Bajtemon，每行包含用单个空格分隔的两个整数 $a_{i}$ 和 $b_{i}$ $(1 \leq a_{i} \leq 5 \cdot 10^{5}, 1 \leq b_{i} < 2^{63})$，分别表示第 $i$ 只 Bajtemon 进化前和进化后的战斗力。注意，进化后的战斗力可能比进化前的小。

输出格式

输出只有一行，包含一个整数，表示 Bajtazar 通过选择战斗力能获得的最大公约数。

样例 1

输入

4
5 7
10 15
13 20
7 5

输出

5

如果字节扎尔选择第三张和第四张卡牌使用进化后的战斗力，而第一张和第二张使用进化前的战斗力，那么最终的战斗力分别是 $5, 10, 20, 5$，它们的最大公约数是 $5$。

样例 2

见附加文件下 [kol1.in](file:kol1.in) 和 [kol1.out](file:kol1.out)。

该样例满足 $n=2; a_{1}=18900, b_{1}=22050, a_{2}=14700, b_{2}=17640$，答案是 $7350$；

样例 3

见附加文件下 [kol2.in](file:kol2.in) 和 [kol2.out](file:kol2.out)。

该样例满足 $n=100000; a_{i}=100000+i, b_{i}=100001+i$，答案是 $2$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$n \leq 5000$	$42$
$2$	无附加限制	$58$