#CW61. 数论对称差(factor)
数论对称差(factor)
题目描述
给定两个正整数 和 。对任意正整数 ,记 为 的质因数集合:如果 是质数且 ,就把 放入 。集合只记录某个质数是否出现,完全忽略它在质因数分解中的次数。例如,,而不是把质因数 重复记录。
我们关心两个集合的对称差 ,也就是恰好属于其中一个集合的质数集合。对于这个集合中的每个质数,把它们各取一次并相乘,得到本题的答案。如果两个数含有完全相同的质因数,那么对称差为空;按照空积约定,此时答案是 。请对每组数据求出这个乘积。
输入格式
从 factor.in 文件中读入。
第一行是测试组数 。接下来有 行,每行给出两个正整数 和 ,表示一组独立询问。不同询问之间没有状态需要继承。
输出格式
从 factor.out 文件中输出。
对每组数据输出一行一个整数,表示 中所有质数的乘积。
样例 1 输入
1
8 9
样例 1 输出
6
样例 1 解释
,,对称差为 ,乘积为 。
样例 2 输入
1
2 4
样例 2 输出
1
样例 2 解释
,对称差为空,按空积约定答案为 。
数据范围
对全部数据,,。
本题采用子任务捆绑计分:一个子任务中的全部测试点均通过后,才能获得该子任务的分数。各子任务分数可以累加。
| 子任务 | 分值 | 测试点 | 附加条件 |
|---|---|---|---|
| 1 | 25 | ||
| 2 | |||
| 3 | |||
| 4 | 完整数据范围 |