质数判断与异或运算在算法题中的应用

1. 题目分析与解题思路

P4752 Divided Prime是一道考察质数判断和数学运算能力的经典算法题。题目要求我们判断两个大数的商是否为质数，这看似简单，实则暗藏玄机。

1.1 问题本质理解

题目给出两个数A和B，其中：

• A = a₁ × a₂ × ... × aₙ
• B = b₁ × b₂ × ... × bₘ

我们需要判断A/B是否为质数。根据题目保证，B的所有因子都包含在A中，所以A/B必定是整数。那么问题的核心就转化为：A/B是否是一个质数？

1.2 关键观察点

1. 质数性质：质数是指大于1的自然数，除了1和它本身外没有其他约数。
2. 因数分解：A/B的结果要成为质数，必须满足：
   • A/B > 1
   • A/B只能被1和它本身整除
3. 因数抵消：由于B的所有因子都包含在A中，所以A/B相当于从A的因数中去掉B的因数后剩下的乘积。

1.3 解题突破口

通过分析可以得出以下结论：

1. 如果A/B=1，不是质数
2. 如果A/B的质因数多于1个，不是质数
3. 剩下的情况就是A/B恰好是一个大于1的质数

2. 算法设计与优化

2.1 朴素解法的问题

最直观的想法是：

1. 计算A的所有质因数
2. 计算B的所有质因数
3. 从A的质因数中去掉B的质因数
4. 检查剩下的质因数是否只有一个，且指数为1

但这种做法对于大数（aᵢ,bᵢ ≤ 10¹²）来说效率太低，无法在时间限制内完成。

2.2 巧妙解法思路

观察题目给出的C++代码，可以发现作者采用了非常巧妙的位运算方法：

1. 异或性质应用：

   • 任何数异或自己等于0
   • 任何数异或0等于它本身
   • 因此，成对出现的数会相互抵消

2. 核心逻辑：

   • 将所有aᵢ和bᵢ合并处理
   • 对aᵢ进行异或，对bᵢ也进行异或（相当于从A中去掉B的因子）
   • 最后剩下的数就是A/B的候选
   • 检查这个数是否是质数

2.3 代码解析

cpp复制#include<cstdio>
using namespace std;
typedef long long ll;

// 快速读取函数
ll re(){
    ll x=