P4752 Divided Prime算法解析与优化

1. 题目背景与核心需求解析

P4752 Divided Prime是信奥竞赛中一道考察数论基础与算法优化的经典题型。题目给定两个整数集合A和B，要求判断A中所有元素乘积除以B中所有元素乘积的结果是否为质数。这道题看似简单，实则暗藏多个需要谨慎处理的边界条件和技术要点。

1.1 题目数学本质

从数学角度分析，题目要求验证表达式(∏A)/(∏B)的质数性。根据算术基本定理，任何大于1的整数都可以唯一分解为质因数的乘积。因此我们需要确保：

1. 最终结果大于1
2. 质因数分解后仅包含一个质数（即其本身）
3. 该结果不能由B集合中的元素抵消后产生（特殊情况处理）

1.2 输入输出特性分析

根据常见竞赛数据范围：

• 集合元素数量n,m ≤ 1e5
• 单个元素值 ≤ 1e12
• 时间限制通常为1秒

这意味着：

• 直接计算乘积会溢出（即使使用long long）
• O(n²)的算法会超时
• 需要线性或线性对数级别的解法

2. 核心算法设计与优化

2.1 质因数分解法

常规思路是对所有数进行质因数分解，然后统计各质因数的总出现次数。但直接分解大数（1e12）效率太低，需要优化：

cpp复制void factorize(long long x, map<long long, int>& factors) {
    for (long long i = 2; i * i <= x; ++i) {
        while (x % i == 0) {
            factors[i]++;
            x /= i;
        }
    }
    if (x > 1) factors[x]++;
}

优化点：

1. 只需遍历到√x即可
2. 用map记录质因数及其次数
3. 处理剩余的大质数情况

2.2 差分计数法

分别处理A和B集合的质因数后，计算它们的差：

cpp复制map<long long, int> diff;
for (auto& [p, cnt] : factorsA) diff[p] += cnt;
for (auto& [p, cnt] : factorsB) diff[p] -= cnt;

最终有效的质因数应满足