思路

二分 + 前缀和。

一个数的因子数等于其 每个质因子 $p_i$ 的数量加1 的乘积，即 $\prod\limits_{i} (cnt_{p_i}+1)$

$q$ 次询问，要求我们单次查询需要控制在 $O(\log n)$ 内。

因为 $10$ 以内只有 $2,3,5,7$ 这 4 个质数，所以可以对这 4 个质数预处理前缀和

假设 $l$ 在第 $i$ 段，$r$ 在第 $j$ 段，那么 $[l+1,j-1]$ 段的可以通过前缀和计算，

单独处理 $i$ 段和 $j$ 段，注意 $i=j$ 的情况即可。

时间复杂度：$O(n\log n)$

代码

C++

// ac
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
#define endl '\n'

int main()
{
  cin.tie(0)->sync_with_stdio(false);
  LL n, m, q;
  cin >> n >> m;
  const int mod = 1e9 + 7;
  vector<int> primes = {2, 3, 5, 7};
  vector<LL> s(m + 1);
  vector<int> a(m + 1);
  vector<array<LL, 4>> pre = vector<array<LL, 4>>(m + 1, {0});
  auto get = [&](int x) -> vector<int> {
          vector<int> cnt(4, 0);
          for (int j = 0;j < 4;++ j) {
                  while(x % primes[j] == 0) {
                          x /= primes[j];
                          ++ cnt[j];
                  }
          }
          return cnt;
  };
  for (int i = 1; i <= m; ++i)
  {
    cin >> a[i] >> s[i];
    pre[i] = pre[i - 1];
    vector<int> cnt = get(a[i]);
    for (int j = 0;j < 4;++ j) {
            pre[i][j] = (pre[i][j] + cnt[j] * s[i]) % mod;
    }
    s[i] += s[i - 1];
  }
  cin >> q;
  while (q --) {
          LL l, r;
          cin >> l >> r;
          int L = lower_bound(s.begin(), s.end(), l) - s.begin();
          int R = lower_bound(s.begin(), s.end(), r) - s.begin();
          vector<int> cnt(4, 0);
          vector<int> cntl = get(a[L]), cntr = get(a[R]);
          LL ans = 1;
          for (int j = 0;j < 4;++ j) {
                  if (L == R) {
                          ans = ((r - l + 1) * cntl[j] % mod + 1) * ans % mod;
                  } else {
                          LL t = (s[L] - l + 1) % mod * cntl[j] % mod;
                   if (L < R) {
                           t += (r - s[R - 1]) % mod * cntr[j] % mod;
                   }
                   if (L + 1 < R) {
                           t += pre[R - 1][j] - pre[L][j];
                   }
                   t = (t % mod + mod) % mod;
                   ans = (t + 1) * ans % mod;
                  }
          }
          cout << ans << endl;
  }
}

Python

# from bisect import bisect_left
n, m = map(int, input().split())
mod = 1000000007

table = {
    1: [0, 0, 0, 0],
    2: [1, 0, 0, 0],
    3: [0, 1, 0, 0],
    4: [2, 0, 0, 0],
    5: [0, 0, 1, 0],
    6: [1, 1, 0, 0],
    7: [0, 0, 0, 1],
    8: [3, 0, 0, 0],
    9: [0, 2, 0, 0],
    10: [1, 0, 1, 0]
}

index = [0 for i in range(1 + m)]
array = [0 for i in range(1 + m)]
pre = [[0 for i in range(4)] for j in range(1 + m)]

for i in range(1, m + 1):
    u, v = map(int, input().split())
    array[i] = u
    u_list = table[u]
    for j in range(4):
        pre[i][j] = (pre[i - 1][j] + u_list[j] * v % mod) % mod
    index[i] = index[i - 1] + v

# print(pre)


def check(index, m, x):
    l = 1
    r = m
    while l <= r:
        mid = (l + r) >> 1
        if index[mid] == x:
            return mid
        elif index[mid] < x:
            l = mid + 1
        else:
            r = mid - 1
    return l


q = int(input())
for i in range(q):
    l, r = map(int, input().split())

    ll = check(index, m, l)
    rl = check(index, m, r)

    # print(ll, rl)
    ans = 1
    lu_list = table[array[ll]]
    ru_list = table[array[rl]]

    for j in range(4):
        if ll == rl:
            ans = ((r - l + 1) * lu_list[j] % mod + 1) * ans % mod
        else:
            tmp = (index[ll] - l + 1) % mod * lu_list[j] % mod
            if ll < rl:
                tmp += (r - index[rl - 1]) % mod * ru_list[j] % mod
            if ll + 1 < rl:
                tmp = (tmp + (pre[rl - 1][j] - pre[ll][j])) % mod
            # tmp = (tmp % mod + mod) % mod
            ans = (tmp + 1) * ans % mod
    print(ans)

题目描述

小美拿到了一个数组，她有$q$次查询，每次询问一个区间内所有元素的乘积有多少因子。你能帮帮她吗?

注:由于数组元素过多，所以是按连续段的方式给定。例如，[1,1,2,3,3,3]有2个1，1个2，3个3，因此表示为<2,1>,<1,2>,<3,3>。

输入描述

第一行输入两个正整数$n,m$，代表数组的大小，以及连续段的数量。 接下来的$m$行，每行输入两个正整数$u_i,v_i$，代表一段区间内有$v_i$个$u_i$

接下来的一行输入一个正整数$q$，代表询问次数。 接下来的$q$行，每行输入两个正整数$l,r$，代表询问的是第$l$个数到第$r$个数的乘积的因子数量

$1\le n\le 10^{14}$

$1\le m,q\le 10^5$

$1\le u_i\le 10$

$1\le v_i\le 10^9$

$1\le l,r\le n$

保证所有的$v_i$之和恰好等于$n$

输出描述

输出$q$行，每行输出一个整数，代表最终的乘积因子数量。由于答案可能过大，请对$10^9+7$取模

样例

输入

6 3
1 2
2 1
3 3
2 
1 3
2 6

输出

2
8