从L到R乘积的计数除数

Question

我一直在解决一个问题，但后来却被它的一部分卡住了，具体如下：

给出了一个N个元素的数组，其第一个元素是Ai，我们得到了L，R类型的Q查询。

对于每个查询输出，从Lth元素到Rth元素的产品除数。

更正式地说，对于每个查询，让我们将P定义为P= AL * AL+1 * AL+2 * ...* AR。

输出P模998244353的除数。

约束条件: 1<= N，Q <= 100000，1<= Ai <= 1000000。

我的方法，

对于每个索引i，我定义了一个map< int，int >，它将素数除数及其计数存储在乘积中，最多可达1，i。

我正在用筛子提取O(LogN)中一个数字的素数除数。

然后，对于每个查询(例如{L，R} )，我将迭代Lth元素的映射，并从Rth元素的映射中减去每个键的计数。

然后我使用结果回答查询:如果N= a^p * b^q * c^r (a，b，c为素数)，则除数为(p+1)(q+1)(r+1)。

上述解的时间复杂度为O(N_D + Q_D)，其中D= 1000000以下不同素数的个数。最坏的情况是D= 78498。

有比这更有效的解决方案吗？

Answer 1

有一个更有效的解决方案。但这有点复杂。以下是实现必要数据结构的步骤。

1. 定义一个数据类型prime_factor，它是一个包含素数和计数的结构，
2. 定义数据类型prime_factorization，该数据类型是第一个数据类型的向量，其大小为素数的升序。这可以存储一个数字的因式分解。
3. 编写了一个接受一个数字的函数，并将它的素因式分解转换为一个prime_factorization函数，该函数接受2个prime_factorization向量，并将它们合并为两个向量的乘积。对于数组中的每个数字，
4. 计算它的素数因式分解。它存储在数组中。
5. 对于数组中的每一对，计算产品的素数因式分解。我们只需要其中的一半。因此，元素0, 1进入一个因式分解，2, 3进入下一个，
6. 重复步骤6 O(log(N))多次。所以你有一个向量，每一个数，对，四，八，等等的因式分解。这导致了近似2N预计算的因式分解向量。大多数向量都很小，尽管有几个可以达到O(D)的大小(其中D是不同素数的数量)。大多数合并应该非常非常快。

现在你已经准备好了所有的数据。它只能占用O(log(N))倍于存储其本身所需的主要因素的空间。(但这比通常情况下要少，因为小素数之间的重复被聚集在一个prime_factor中。)

任何范围最多都是这些计算向量的O(log(N))的并。例如，范围10..25可以分解为10..11, 12..15, 16..24, 25。将这些间隔从最小到最大排列，并合并它们。然后根据结果计算出你的答案。

精确的分析是复杂的。但是，我向您保证，查询时间在O(Q * D * log(N))之上是有界的，并且通常比这少得多。

更新

你觉得这些时间间隔如何？

答案是，您需要确定在范围内可被2的最高幂整除的数字，然后从那里填出两边。然后把它除以2(四舍五入)，直到范围为1，然后把上边界乘以2，找到中点。

例如，如果您的范围是35-53，那么从除以2开始，得到35-53、17-26、8-13、4-6、2-3。那是我们分开的2^4。我们的2中点的幂是3*2^4 = 48.我们在中点以上的间隔是48-52, 53-53。下面的间隔是40-47, 36-39, 35-35。它们的长度是2的幂，从一个可以被2的幂整除的数开始。