algorithm - 计算给定数 N 的 "cool"个除数

Question

我正在尝试用除数和数论解决相当复杂的问题。

也就是说，对于给定的数字 m，我们可以说 k 是很酷的除数，如果 k<m < em>k|m(k 整除 m)，对于给定的数 n，数 k^n(k 的 n 次方)是不是 m 的除数。设 s(x) - x 的冷除数数。

现在对于给定的 a 和 b，我们应该找到 D = s(a) + s(a+1) + s(a+2) + s(a+3) + ... + s(a+b) .

所有值的限制:(1 <= a <= 10^6), (1 <= b <= 10^7), (2<=n<=10)

示例

假设 a=32，b=1，n=3；

x = 32，n = 32 的 3 个约数是 {1,2,4,8,16,32}。然而只有 {4,8,16} 满足条件所以 s(32) = 3

x = 33，n = 33 的 3 个约数是 {1,3,11,33}。只有数字{3,11}满足条件所以s(33)=2;

D = s(32) + s(33) = 3 + 2 = 5

我尝试过的

我们应该在 3 秒的时间限制内回答所有 100 个测试用例的问题。

我有两个想法，第一个:我在区间 [a, a+b] 中迭代，对于范围内的每个值 i，我检查该值有多少个很酷的除数，我们可以在 O 中检查这个(sqrt(N)) 如果获取 N 的幂数的函数被认为是 O(1)，那么总的函数是 O(B*sqrt(B))。

第二个，我现在确定它是否有效以及速度有多快。首先我进行预计算，我有一个从 1 迭代到 N 的 for 循环，其中 N = 10^7现在在 [2, N] 范围内，对于每个除数为 i 的数字，其中 i 在 [2,N] 范围内，我检查我的 n 次方是否不是 j 的除数，然后我们更新该数字j 还有一个很酷的除数。有了这个，我认为复杂度将是 O(NlogN)，而答案是 O(B)。

Answer 1

您的第一个想法可行，但您可以改进它。

您可以分解 N=*p0^q0*p1^q1*p2^q2...pk^qk*，而不是检查从 1 到 sqrt(N) 的所有数字是否是很酷的除数。那么冷除数的数量应该是 (q0+1)(q1+1)...(qk+1) - (q0/n+1)(q1/n+1).. .(qk/n+1).

因此，您可以首先使用埃拉托色尼筛法 等现有算法预处理并找出所有质数，然后对 [a,a+b] 之间的每个数字 N 进行因式分解。复杂度应该大致为 O(BlogB)。

您的第二个想法也可行。

对于 [2,a+b] 之间的每个数字 i，您可以只检查 [a,a+b] 之间 i 的倍数，看看 i 是否是这些倍数的除数。复杂度也应该是 O(BlogB)。这个想法可以发挥一些技巧来加速程序，一旦你不需要时不时地使用除/模操作来检查我是否是一个很酷的除数。您可以计算 [a, a+b] 之间的第一个数字 m，即 i^n|m。这个 m 应该是 m=ceiling(a/(i^n))(i^n)。然后你知道 i^n|m+p*i 不适用于 [1,i^(n-1) - 1] 之间的 p 并且适用于 p=i^n-1。基本上，您知道 i 不是每 i^(n-1) 倍的一个很酷的除数，并且您不需要使用除法/模来计算它，这将加快程序速度。