题解：P5946 [POI 2002] B-Smooth 数

徐晨轩✅ · 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;
}