质因数分解与区间乘积整除性算法解析

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

P7281 [COCI 2020/2021 #4] Vepar是克罗地亚信息学竞赛的一道经典题目，主要考察选手对整数因子分解和前缀和算法的掌握程度。题目要求我们判断给定的两个区间[a,b]和[c,d]中所有整数的乘积是否能被另一个区间[e,f]中所有整数的乘积整除。

这个问题的实际意义在于模拟现实中的批量验证场景。比如在密码学中，我们需要快速验证大量密钥的因子构成；在数学研究中，可能需要分析多项式系数的整除关系。题目通过区间乘积的形式，将单个数的因数判断扩展到了集合层面。

2. 解题思路与算法选择

2.1 暴力法的局限性

最直观的想法是直接计算三个区间的乘积然后做除法判断。例如：

cpp复制long long productA = 1;
for(int i=a; i<=b; i++) productA *= i;
// 同理计算productC和productE
if(productA * productC % productE == 0)...

但这种方法存在两个致命缺陷：

1. 当区间较大时（比如1e5），乘积会迅速超出long long的范围
2. 即使使用大整数，时间复杂度O(b-a+d-c+f-e)也难以承受

2.2 质因数分解法

更聪明的做法是将问题转化为质因数的比较。根据算术基本定理，任何正整数都可以唯一表示为质数的乘积。因此，我们可以：

1. 对区间[a,b]和[c,d]中每个数分解质因数，统计每个质数的总次数
2. 对区间[e,f]做同样操作
3. 检查第一个质因数集合是否包含第二个集合的所有质因数，且次数不小于

这种方法将乘积的整除性问题转化为质因数的包含关系问题。

3. 核心算法实现细节

3.1 埃拉托斯特尼筛法优化

为了快速分解质因数，我们需要预先计算质数表。使用埃氏筛可以在O(n log log n)时间内筛出[1,1e7]范围内的所有质数：

cpp复制const int MAX = 1e7;
vector<bool> isPrime(MAX+1, true);
void sieve() {
    isPrime[0] = isPrime[1] = false;
    for(int i=2; i*i<=MAX; i++)