质因数分解在区间乘积整除判断中的应用

1. 题目解析与解题思路

1.1 问题本质分析

这道题目要求我们判断两个连续整数区间乘积的整除关系。具体来说，给定区间[a,b]和[c,d]，我们需要判断区间[c,d]内所有整数的乘积是否能被区间[a,b]内所有整数的乘积整除。

从数学角度看，这实际上是在比较两个阶乘的比值：即(b!/(a-1)!)能否整除(d!/(c-1)!)。直接计算这两个大数的乘积在实际操作中会遇到两个主要问题：

1. 数值溢出：当区间范围较大时（如题目中的10^7），直接相乘会导致数值远远超过普通数据类型的表示范围
2. 效率问题：对于每组测试数据都重新计算乘积，时间复杂度会非常高，无法在合理时间内完成

1.2 质因数分解思路

更聪明的做法是利用数论中的质因数分解原理。根据算术基本定理，任何大于1的正整数都可以唯一地表示为一系列质数的乘积。因此，我们可以将问题转化为：

对于每一个质数p，检查在区间[a,b]的乘积中p的幂次是否不超过在区间[c,d]的乘积中p的幂次。

具体来说，对于质数p，我们需要计算：

1. 区间[a,b]乘积中p的幂次：count_p(a,b)
2. 区间[c,d]乘积中p的幂次：count_p(c,d)

如果对于所有质数p，都有count_p(a,b) ≤ count_p(c,d)，那么答案就是"DA"（可以整除），否则是"NE"（不能整除）。

1.3 质数幂次的高效计算

计算一个区间乘积中某个质数p的幂次，可以使用Legendre公式的变体。对于一个数n!中质数p的幂次，公式为：

count_p(n!) = ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + ...

对于区间[a,b]的乘积，其中p的幂次为：
count_p(a,b) = count_p(b!) - count_p((a-1)!)

同理，区间[c,d]的乘积中p的幂次为：
count_p(c,d) = count_p(d!) - count_p((c-1)!)

2. 算法实现细节

2.1 素数筛法优化

为了高效处理大范围内的质数，我们需要使用筛法预先计算质数。题目中数据范围达到10^7，因此我们采用优化的埃拉托斯特尼筛法：

cpp复制const int maxn = 10000005;
bool vis[maxn];