algorithm - 这个问题可以用动态规划解决吗？

Question

给定n、m、d。答案存储在以下代码的 sum 变量中:

int x = m / d;
int sum = 0;
for (int i = 1; i <= x; i++) {
    sum += mobius(i) * ((x / i) ^ n);
}

现在的问题是当 d 与 [l, r] 不同时，找到总的 sum % (10^9 + 7)与 n, m 如上所述。我只能通过蛮力做到这一点，但限制是 1 <= n, m, l, r <= 10^7。所以暴力破解无法通过时间限制。该问题是否存在一些潜在的重叠子问题和最优子结构性质，可用于动态规划求解？

链接:Mobius Function ，我已经在O(nlogn)中预先计算了莫比乌斯函数。
编辑:给定 t、n、m。其中t是测试用例的数量，
l, r 被赋予 t 次。如上所述，我们必须输出总和。

示例输入:
总人数:2
男:3，女:10
l 和 r
的值9 9
10 10

示例输出:
1
1

Answer 1

请注意，当您将 m 除以 d 来计算 x 时，x 将只有大约 2*sqrt(m) 个唯一值。

这意味着您只需为 x 的每个唯一值触发第二个循环。

同样，在x/i的计算中，(x/i)<只会有大约2*sqrt(x)个唯一值。这意味着您只需为每个唯一值计算 (x/i)^n。

对于 x/i 的每个唯一值，都会有一系列 i 值产生该值。

然后，您需要将产生相同输出的所有 i 值相加 mobius[i]。这可以通过用莫比乌斯函数的累积和准备一个数组来完成(这个累积和称为 Mertens function )。

例如，如果

M[k] = sum[ Mobius(i) for i = 1..k ]

然后

sum[ Mobius(i) for i = low..high ] = M[high] - M[low-1]

总体而言，复杂度为 O( sqrt(n) * sqrt(n) ) = O(n)(加上计算莫比乌斯函数所花费的时间)。