自动搬运

查看原文

来自洛谷，原作者为

	徐晨轩✅ https://discord.gg/bNTY6ThGZD

搬运于2025-08-24 22:15:52，当前版本为作者最后更新于2025-02-02 18:33:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

差分转化为求 $[1,x]$ 之间的 B-smooth 数。

记忆化搜索。先预处理出所有 $\le B$ 的质数。令 $f(x,i)$ 表示搜完前 $i-1$ 个质数，剩下的乘积 $\le x$ 的方案数。显然有 $f(x,i)=f(x,i+1)+f(\dfrac{x}{p_i},i)$ ，其中 $p_i$ 为第 $i$ 个质数。$f(x,1)$ 即为答案。

注意剪枝：如果 $p_i ^ 2 > x$，显然剩下的只能是单个质数（或者是 $1$）。二分即可统计方案数。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1000005;

int l, r, p, np[N];
vector<int> pr;
unordered_map<int, int> mem;

void init(int n) {
    for (int i = 2; i <= n; i++) {
        if (!np[i])
            pr.push_back(i);
        for (int j : pr) {
            if (i * j > n) break;
            np[i * j] = 1;
            if (i % j == 0) break;
        }
    }
}

int count_primes(int x, int i) {
    int l = i, r = pr.size() - 1, ans = i;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (pr[mid] <= x) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    return ans - i + 1;
}

int dfs(int x, int i = 0) {
    if (x < 1) return 0;
    if (i >= pr.size() || pr[i] > x) return 1;
    if (pr[i] * pr[i] > x) return count_primes(x, i) + 1;
    int id = x * pr.size() + i;
    if (mem.count(id)) return mem[id];
    return mem[id] = dfs(x, i + 1) + dfs(x / pr[i], i);
}

signed main() {
    cin >> l >> r >> p;
    r += l;
    init(p);
    cout << dfs(r) - dfs(l - 1) << endl;
    return 0;
}