#P5881. 【化学】实验

    ID: 4802 远端评测题 1400ms 125MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>图论并查集江苏O2优化素数判断质数筛法

【化学】实验

题目背景

小 Z 紧张地坐在了一张化学实验桌前,进行着化学实验。

教室里又传来了一阵哀叹声:

我…我好像又错了…我能再试一次吗?

题目描述

在她的面前,摆放着 nn 个试管。试管里装着不明液体。对于每种不明液体,有 22 个已知的化学属性:aabb。第 ii 种液体的两个属性值分别为 aia_ibib_i

现在,老师给她布置了 mm 个实验。

对于每一次实验,有一个参照量 xx(第 ii 次实验的参照量记作 xix_i)。她需要把不明液体分成尽可能多的组,且满足:任意两种不同组的液体iijjgcsd(ai,aj)\operatorname{gcsd(a_i,a_j)} 都不能大于 x2x^2

其中 gcsd\operatorname{gcsd} 代表他们的最大公约平方数。kk是两个数的公约平方数,当且仅当满足以下两个条件:

  • kk 为这两个数的公约数;

  • kk 为完全平方数。

而最大公约平方数 gcsd\operatorname{gcsd} 为所有满足条件的 kk 中的最大者。

形象的说, gcsd\operatorname{gcsd} 可以理解成两个数的最大公约数的算术平方根的整数因式部分的平方。

例如:

gcsd(24,64)\operatorname{gcsd(24,64)},就是先求出 24,6424,64 的最大公约数,是 88 ,然后 8=22\sqrt 8=2\sqrt 2,其整数因式是 22,所以 gcsd(24,64)=22=4\operatorname{gcsd(24,64)}=2^2=4

她还需要在分组数最多的情况下,使自己的实验得分最大。

实验得分的定义:对于每一种试剂,定义其得分 cic_ibib_i 分解质因数之后最大的指数

例如:bi=12=22×31b_i=12=2^2\times 3^1ci=max{2,1}=2c_i=\max\{2,1\}=2

bi=90=21×32×51b_i=90=2^1\times 3^2\times 5^1ci=max{1,2,1}=2c_i=\max\{1,2,1\}=2

而实验得分即为所有组内的 cic_i 的最大值之和。

当然,她的 IQIQ 并不高,所以需要请求你的帮助。

输入格式

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

第二行 nn 个整数 a1na_{1\dots n}

第三行 nn 个整数 b1nb_{1\dots n}

第四行 mm 个整数 x1mx_{1\dots m}

输出格式

mm 行,对于第 ii 行,输出 22 个整数:第 ii 次试验的组数和实验得分。

5 5
36 72 4 9 16
2 4 6 8 10
2 3 4 5 6

3 5
4 7
4 7
4 7
5 8

提示

样例解释 #1

b1=2=21,c1=1b_1=2=2^1,c_1=1

b2=4=22,c2=2b_2=4=2^2,c_2=2

b3=6=21×31,c3=max{1,1}=1b_3=6=2^1\times 3^1,c_3=\max\{1,1\}=1

b4=8=23,c4=3b_4=8=2^3,c_4=3

b5=10=21×51,c5=max{1,1}=1b_5=10=2^1\times 5^1,c_5=\max\{1,1\}=1

x=2x=2 时,可分为三组:{1,2,4},{3},{5}\{1,2,4\},\{3\},\{5\}

实验得分为max{1,2,3}+max{1}+max{1}=5\max\{1,2,3\}+\max\{1\}+\max\{1\}=5


数据范围

「本题采用捆绑测试」

subtask nn\le mm\le aia_i \le bib_i\le xx \le 分值
11 44 66 100100 4×1044 \times 10^4 100100 55
22 88 77 2020 10310^3 1010
33 2020 3030 5050 8×1038 \times 10^3 100100 1010
44 100100 6060 100100 4×1044 \times 10^4 10310^3
55 5×1035 \times 10^3 110110 10310^3 10510^5 4×1034 \times 10^3
66 2×1042 \times 10^4 250250 3×1033 \times 10^3 10610^6 3×1033 \times 10^3
77 5×104 5 \times 10^4 10310^3 10410^4 2×1072 \times 10^7 1.5×1041.5 \times 10^4 1515
88 10510^5 8×1038 \times 10^3 2×1042 \times 10^4 2.2×1042.2 \times 10^4
99 2×1052 \times 10^5 4×1044 \times 10^4 3×1043 \times 10^4 2020

对于 100%100\% 的数据:

1n,m2×1051 \le n,m \le 2\times 10^52ai4×1042 \le a_i \le 4\times 10^42bi2×1072 \le b_i \le 2\times 10^72x3×1042 \le x \le 3\times 10^4

\dots我好像又错了\dots我能再试一次吗?