T1互质划分（coprime）

题目描述

正整数 aa 和 bb 的最大公因数是满足 a,ba,b 同时是 dd 的倍数的最大的正整数 dd。

而正整数 aa 和 bb 互质，指的是 aa 和 bb 的最大公因数为 11。

给定一个正整数 nn，求最少把 1∼n1\sim n 共 nn 个正整数分成多少堆，才能使得每一堆里面每两个数都互质。

输入格式

一行一个正整数 nn。

输出格式

一行一个整数表示最少的堆数。

样例 1 输入

2

样例 1 输出

1

样例 1 解释

一种合法方案是把 1,21,2 放在同一堆，则 1,21,2 的最大公因数是 11，它们互质，所以满足要求。

样例 2 输入

5

样例 2 输出

2

样例 2 解释

一种合法方案是把 1,2,51,2,5 放在同一堆，3,43,4 放在同一堆，可以验证是满足要求的。

数据规模与约定

对于 50%50\% 的数据，1≤n≤101\leq n\leq 10。

对于 70%70\% 的数据，1≤n≤1031\leq n\leq 10^3。

对于 100%100\% 的数据，1≤n≤10181\leq n\leq 10^{18}。

T2出租车（taxi）

题目描述

A 城是一个独特的城市，因为它是一条无尽的数轴。

打车软件 U 如今非常流行，其被城市中所有的 mm 名出租车司机使用，他们每天运送剩下的城市居民——nn 名乘客。

A 城的每个居民（包括出租车司机）都住在一个独一无二的位置，也就是说没有两个居民的坐标是相同的。

U 的系统非常聪明：当乘客叫车时，他的呼叫不会传给所有的出租车司机，而只会传给离他最近的那个司机。如果有多个司机距离相同，那么坐标较小的司机会收到呼叫。

但是，有一天早上，出租车司机们好奇：当一个乘客是当天第一个叫车的，会有多少乘客选择给指定的出租车司机打电话？换句话说，你需要为每个出租车司机 ii 找到 aia_i——当所有司机和乘客都在家时，会有多少乘客选择给第 ii 名出租车司机打电话？

出租车司机不能接送自己或呼叫其他出租车司机。

输入格式

第一行两个正整数 n,mn,m。

第二行 n+mn+m 个正整数 x1,x2,⋯ ,xn+mx_1,x_2,\cdots,x_{n+m}，其中 xix_i 表示第 ii 位居民的家的位置。

第三行 n+mn+m 个整数 t1,t2,⋯ ,tn+mt_1,t_2,\cdots,t_{n+m} 表示每个居民的身份，如果 ti=1t_i=1，那么第 ii 个居民是司机，否则他是乘客。

保证 ti=1t_i=1 的 ii 的数量恰为 mm。

输出格式

一行 mm 个整数 a1,a2,⋯ ,ama_1,a_2,\cdots,a_m，其中 aia_i 是第 ii 名出租车司机的答案。家坐标第 ii 小的出租车司机编号为 ii。

样例 1 输入

3 1
1 2 3 10
0 0 1 0

样例 1 输出

3

样例 1 解释

只有一个出租车司机，这意味着所有 nn 名乘客的订单都会传给他。

样例 2 输入

3 2
2 3 4 5 6
1 0 0 0 1

样例 2 输出

2 1

样例 2 解释

第一个出租车司机住在坐标为 22 的点，第二个出租车司机住在坐标为 66 的点。显然，住在坐标 33 的乘客最接近第一个出租车司机，而住在坐标 55 的乘客最接近的是第二个出租车司机。住在坐标 44 的乘客与第一个和第二个出租车司机的距离相同，但因为第一个出租车司机的坐标较小，所以这个乘客的呼叫会传给第一个出租车司机。

样例 3 输入

1 4
2 4 6 10 15
1 1 1 1 0

样例 3 输出

0 0 0 1

样例 3 解释

有一个乘客，离他最近的是第四个出租车司机。

数据规模与约定

对于 40%40\% 的数据，1≤n,m≤10001\leq n,m\leq 1000。

对于另外 30%30\% 的数据，司机全部在一个区间内，即存在区间 [l,r]⊆[1,n+m][l,r]\subseteq [1,n+m]，满足 r−l+1=mr-l+1=m，且对于所有 l≤i≤rl\leq i\leq r，均有 ti=1t_i=1。

对于 100%100\% 的数据，1≤n,m≤1051\leq n,m\leq 10^5，1≤x1<x2<⋯<xn+m≤1091\leq x_1<x_2<\cdots<x_{n+m}\leq 10^9，0≤ti≤10\leq t_i\leq 1，ti=1t_i=1 的 ii 恰有 mm 个。

T3木雕玩具（toy）

题目描述

在一个小镇上，有一个专门从事木雕工艺的工作室。由于小镇规模不大，只有三位雕刻师在那里工作。

小镇上计划举办一个木制玩具节。工作室的员工们想要为此做好准备。

将会有 nn 个人来到工作室请求制作木制玩具。每个人都是独一无二的，他们可能想要不同的玩具。为了简化问题，让我们用 aia_i 表示第 ii 个人想要的玩具图案。

每位雕刻师都可以事先选择一个图案，用一个 11 到 10910^9 之间的整数 xx 来表示，不同的雕刻师可以选择不同的图案。在节日准备期间，雕刻师将完全掌握制作所选图案玩具的技巧，这将使他们能够立刻切割出木制玩具。对于选择了图案 xx 的雕刻师来说，制作图案为 yy 的玩具将需要 ∣x−y∣|x-y| 的时间，因为玩具图案越接近他能立即制作的，雕刻师就越能快速完成工作。

在节日当天，当一个人来到工作室请求制作木制玩具时，雕刻师可以选择谁来接手这份工作。同时，雕刻师们都是非常熟练的人，可以同时为不同的人工作。

由于人们不喜欢等待，雕刻师们希望选择准备的图案，使得所有人的最大等待时间尽可能小，请你求出这个值。

输入格式

第一行包含一个整数 nn 表示来到工作室的人数。

第二行包含 nn 个整数 a1∼na_{1\sim n} 表示玩具的图案。

输出格式

一行一个整数表示答案。

样例 1 输入

6
1 7 7 9 9 9

样例 1 输出

0

样例 1 解释

三位雕刻师事先选择图案 1,7,91,7,9。

样例 2 输入

6
5 4 2 1 30 60

样例 2 输出

2

样例 2 解释

三位雕刻师事先选择图案 3,30,603,30,60。

样例 3 输入

9
14 19 37 59 1 4 4 98 73

样例 3 输出

13

样例 3 解释

三位雕刻师事先选择图案 14,50,8514,50,85。

数据规模与约定

对于 30%30\% 的数据，1≤n≤101\leq n\leq 10，1≤ai≤1001\leq a_i\leq 100。

对于 50%50\% 的数据，1≤n≤20001\leq n\leq 2000，1≤ai≤1001\leq a_i\leq 100。

对于 70%70\% 的数据，1≤n≤20001\leq n\leq 2000。

对于 100%100\% 的数据，1≤n≤2×1051\leq n\leq 2\times 10^5，1≤ai≤1091\leq a_i\leq 10^9。

T4幽默数（humor）

题目描述

给定一个长度为 nn 的正整数序列 aa。一个正整数 xx 被称为「幽默的」，当且仅当不存在一个子区间，使得其所有元素的最小公倍数等于 xx。

你需要找到最小的「幽默的」数。

序列 aa 的子区间指的是序列中的一组元素 al,al+1,⋯ ,ara_l,a_{l+1},\cdots,a_r，其中 1≤l≤r≤n1\leq l\leq r\leq n。我们将这样的子区间表示为 [l,r][l,r]。

输入格式

第一行一个整数 TT 表示数据组数。

对于每组数据，第一行一个整数 nn，第二行 nn 个整数 a1∼na_{1\sim n}。

输出格式

对于每组数据，输出一行一个整数表示答案。

样例 1 输入

6
3
1 2 3
5
1 2 3 4 5
2
2 3
1
1000000000
12
1 8 4 2 3 5 7 2 9 10 11 13
12
7 2 5 4 2 1 1 2 3 11 8 9

样例 1 输出

4
7
1
1
16
13

样例 1 解释

在第一组样例数据中，44 是一个幽默数，并且是最小的，因为数组中出现了整数 1,2,31,2,3，这意味着存在长度为 11 的子区间，其最小公倍数分别为 1,2,31,2,3，并且不存在最小公倍数等于 44 的子区间。

在第二组样例数据中，77 是一个幽默数，整数 1∼51\sim 5 明确出现在数组中，而整数 66 是子区间 [2,3][2,3] 和 [1,3][1,3] 的最小公倍数。

在第三组样例数据中，11 是一个幽默数，因为子区间 [1,1],[1,2],[2,2][1,1],[1,2],[2,2] 的最小公倍数分别为 2,6,32,6,3。

数据规模与约定

对于 20%20\% 的数据，1≤n≤1001\leq n\leq 100。

对于 40%40\% 的数据，1≤n≤10001\leq n\leq 1000。

对于另外 30%30\% 的数据，1≤ai≤1051\leq a_i\leq 10^5。

对于 100%100\% 的数据，1≤T≤101\leq T\leq 10，1≤n≤1051\leq n\leq 10^5，1≤ai≤1091\leq a_i\leq 10^9。