#CW61. 数论对称差(factor)

数论对称差(factor)

题目描述

给定两个正整数 xx 和 yy。对任意正整数 zz,记 P(z)P(z) 为 zz 的质因数集合:如果 pp 是质数且 p∣zp\mid z,就把 pp 放入 P(z)P(z)。集合只记录某个质数是否出现,完全忽略它在质因数分解中的次数。例如,P(12)={2,3}P(12)=\{2,3\},而不是把质因数 22 重复记录。

我们关心两个集合的对称差 P(x)△P(y)P(x)\triangle P(y),也就是恰好属于其中一个集合的质数集合。对于这个集合中的每个质数,把它们各取一次并相乘,得到本题的答案。如果两个数含有完全相同的质因数,那么对称差为空;按照空积约定,此时答案是 11。请对每组数据求出这个乘积。

输入格式

从 factor.in 文件中读入。

第一行是测试组数 TT。接下来有 TT 行,每行给出两个正整数 xx 和 yy,表示一组独立询问。不同询问之间没有状态需要继承。

输出格式

从 factor.out 文件中输出。

对每组数据输出一行一个整数,表示 P(x)△P(y)P(x)\triangle P(y) 中所有质数的乘积。

样例 1 输入

1
8 9

样例 1 输出

6

样例 1 解释

P(8)={2}P(8)=\{2\},P(9)={3}P(9)=\{3\},对称差为 {2,3}\{2,3\},乘积为 66。

样例 2 输入

1
2 4

样例 2 输出

1

样例 2 解释

P(2)=P(4)={2}P(2)=P(4)=\{2\},对称差为空,按空积约定答案为 11。

数据范围

对全部数据,1≤T≤1061\le T\le 10^6,2≤x,y≤1072\le x,y\le 10^7。

本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。

子任务 分值 测试点 附加条件
1 25 1∼51\sim 5 x,y≤10x,y\le 10
2 6∼106\sim 10 x,y≤100x,y\le 100
3 11∼1511\sim 15 x,y≤105x,y\le 10^5
4 16∼2016\sim 20 完整数据范围