前置知识:线性筛法、前缀和
字丑勿喷
样例模拟
这里只模拟样例 $1$ 的问题 $1$
解释一下公式:
设有集合 $x$ (就是输入的 $x_i$ )
$f(p)$ 就是一个函数,表示 $p\mid x_i$ 的个数
$S$ 表示 $[l, r]$ 区间的质数集合
$\sum\limits_{p\in S}f(p)$ 先设 $k_i$ 是 $[l,r]$ 区间的质数,对于每个 $x_i$ 能 $k_i\mid x_i$ 的数的个数。
解题思路
这是一道偏数学的题目,看到题目后发现 $l$ 和 $r$ 很大,再看到要回答问题答案,那么就有可能是要预处理了,看到 $x_i$ 这么小,$l$ 有可能大于 $x_i$ 那么这道题就很简单了。
先分类讨论一下,如果 $x_i < l$ 那么输出 $0$。
如果 $x_i \ge$ 那么就输出 $s_{min(10^7, r)}-s_{l-1}$
用 $a_i$ 表示 $x$ 集合中能整除 $i$ 的个数,那么 $s_i$ 就是 $a_i$ 的前缀和,也就是 $s_i=a_1+a_2+…+a_i=\sum\limits_{j=1}^{i}a_j$。
现在预处理出 $a_i$ 就行了,可以这样预处理对于每个 $x_i$ 我们一直除以它的最小质因子,直到不能再除,除完之后,再用除出来的数,也就是这个数中的因数中没有 $x_i$ 的最小质因子了,我们再找到这个数的最小质因子,继续除,重复上面操作,直到这个数等于 $1$ 为止。用 $q_j$ 表示每个最小质因子,那么 $a_{q_j}$ 加 $1$ 就行了。
最小质因子可以用线性筛求出,至于为什么请看下面。
代码:
// 可以忽略掉
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mem(x, a) memset(x, a, sizeof x)
#define q_r \
ios::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0);
#define swap(a, b) a = a ^ b, b = b ^ a, a = a ^ b
#define all(x) x.begin(), x.end()
#define pb push_back
#define endl '\n'
using ll = long long;
using db = double;
using ull = unsigned long long;
const int INF = 0x3f3f3f3f;
#define rep(x, y, z) for (int x = y; x <= z; ++x)
#define per(x, y, z) for (int x = y; x >= z; --x)
#define sc scanf
#define pr printf
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<double, double>;
#define pu(ch) putchar(ch)
#define ge() getchar()
inline int read() {
int s = 0, fu = 1;
char ch = ge();
while (ch < '0' || ch > '9') {if (ch == '-') fu = -1; ch = ge();}
while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = ge();
return s * fu;
}
// --------------------------------------------------------------------------------------------------------------------------------
const int MAXN = 1e7 + 10;
bool st[MAXN];
int primes[MAXN], cnt, d[MAXN], n, x, m, a[MAXN], s[MAXN];
void get_primes(int n) { // 线性筛
for (int i = 2; i <= n; ++i) {
if (!st[i]) {
primes[cnt++] = i, d[i] = i;
}
for (int j = 0; primes[j] <= n / i; ++j) {
st[i * primes[j]] = true;
d[i * primes[j]] = primes[j]; // primes[j] * i 的最小质因子是 primes[j]
if (i % primes[j] == 0) break;
}
}
}
void solve() {
get_primes(1e7);
n = read();
for (int i = 1; i <= n; ++i) {
x = read();
while (x > 1) {
int p = d[x];
++a[p];
while (x % p == 0) x /= p;
}
}
for (int i = 1; i <= 1e7; ++i) // 前缀和
s[i] = s[i - 1] + a[i];
m = read();
while (m--) {
int l = read(), r = read();
if (l > 1e7) puts("0");
else {
pr("%d\n", s[min((int)1e7, r)] - s[l - 1]);
}
}
}
int main() {
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
线性筛
可以听这个
但对于时间复杂度怎么算他好像算错了,因该是每个数都会被筛掉一次,所以是 $O(n)$
前缀和
可以听这个
有错误还请纠正