#P2579. Fight with function

Fight with function

题目描述

积性函数是指具有性质 f(m∗n)=f(m)∗f(n)f(m*n)=f(m)*f(n) 的一类函数。现在我们对一个积性函数f增加一个限制条件:如果 mm 与 nn 互质,则 f(m)f(m) 与 f(n)f(n) 也互质,并且一定有 f(1)=1f(1)=1 。函数 ff 的定义域和值域都是正整数。 现在,你被提供了一些 xx 以及相对应的 f(x)f(x) 的值。你的任务是对于每一个询问的 yy ,判断 f(y)f(y) 的值是否唯一,如果唯一,输出 f(y)f(y) 的值。

输入格式

输入的第一行包含了测试点的个数。对于每一个点,第一行包含了一个整数 NN ,这是提供的 (x,f(x))(x,f(x)) 的对数。接下来 NN 行,每行的有两个被空格分开的数,第一个是 xx 值,第二个是其对应的 f(x)f(x) 值。下一行是询问的个数 qq 。下面 qq 行每行包含了一个询问的 yy 。

输出格式

对于每一个测试点输出 qq 行,每一行对应一个询问。如果给出的数据与函数f的性质不符或者不能凭借给出的数据确定惟一的 f(y)f(y) ,输出 NO,否则输出YES f(y),其中的 f(y)f(y) 被替换成 f(y)f(y) 的值,不能包含前导 00 。

3
3
2 2
3 2
7 19
1
7
1
6 6
1
6
2
2 2
3 3
1
12
NO
YES 6
YES 12

提示

测试点的个数小于 2020 , N≤50N \le 50 ,给出的 xx 和 f(x)f(x) 都不大于 105010^{50} 。

xx 与 f(x)f(x) 都没有大于 100005100005 的质因数。