洛谷P1748 H数 题解

题目链接：P1748 H数

题意：

所谓 \(H\) 数，是指只含有 \(2,3,5,7\) 这些质因数的数，如 \(630\) 是 \(H\) 数，而 \(22\) 不是。

现在要求输出第 \(n\) 个 \(H\) 数，即 \(H_n\) （为了方便起见将 \(H_1\) 定为 \(1\) ）。

已知 \(n\) 不超过 \(10000\)，最后数据在 int64 范围之内。

输入格式：

一行， \(n\) 。

输出格式：

一行，输出 \(H_n\)​ 。

虽说是 普及/提高− 的题，但是它的思路还是挺有意思的。

考虑dp，或者说考察 \(H_n\) 的递推方式。 \[ H_i=\min\{H_a\times 2,~H_b\times 3,~H_c \times 5,~H_d\times 7\} \] 其中 \(a,b,c,d\) 均满足特定形式，例如 \(H_{a-1}\times 2 \le H_i < H_a \times 2\) 。

一种暴力的转移方式是，枚举 \(j\) ，并钦定：例如当 \(j\) 满足 \(a\) 的条件时尝试用 \(H_a\) 更新 \(H_i\) 。

这样只需扫一遍 \([1,~i-1]\) 即可。注意到 \(a,b,c,d\) 均随着 \(i\) 的增长而不减。

因此我们可以直接维护四个指针 \(a,b,c,d\) ，每次算出 \(H_i\) 后，更新 \(a,b,c,d\) 使他们重新满足条件。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e4 + 15))

int a,b,c,d,x[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n; x[1] = a = b = c = d = 1;
    for(int i = 2; i <= n; i++)
    {
        x[i] = x[a] * 2;
        if(x[i] > x[b] * 3) x[i] = x[b] * 3;
        if(x[i] > x[c] * 5) x[i] = x[c] * 5;
        if(x[i] > x[d] * 7) x[i] = x[d] * 7;
        if(x[i] == x[a] * 2) ++a;
        if(x[i] == x[b] * 3) ++b;
        if(x[i] == x[c] * 5) ++c;
        if(x[i] == x[d] * 7) ++d;
    }
    cout << x[n] << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/blog/user41920/solution-p1748

---

题外话：

这和 H 有什么关系？