AtCoder Beginner Contest 300G - P-smooth number解题报告

AtCoder Beginner Contest 300G - P-smooth number解题报告

1 题目链接

传送门

2 题目大意

题目：P-光滑数的数量

题目大意：

在 $1$ 到 $n$ 中，有多少个数的所有质因数均不超过 $p(p\le 100)$。

3 解法分析

这道题看着很像搜索，于是你可以写出来一份 $TLE$ 代码。

$dfs(x,y)$ 表示在 $(x,prm[y])$ 下单答案。
其中 $prm[37]$ 来存下 $100$ 内的所有质数，因只有 $25$ 个所以不如打表。

接下来考虑优化。

首先就是一个记忆化搜索，然后再剪枝。

十分显然的，从大质数向小质数搜可以有效避免无意义的搜索。

于是复杂度玄学起来，你也就 $AC$了。

4 解法总结

记搜+剪枝。

5 AC Code

#include <bits/stdc++.h>
#define int long long
#define N 1000000
using namespace std;int ans;
int n, m, inf;
int dp[26][2000007];int prm[37] = {2, 3, 5, 7,11, 13, 17, 19,23, 29, 31, 37,41, 43, 47,53, 59, 61, 67,71, 73, 79,83, 89, 97,1145141919810
};void dfs(int x, int y) {if (x <= N && dp[y][x]) {ans += dp[y][x];return ;}if (!y) {ans = ans + __lg(x) + 1;return ;}int cnt = ans;dfs(x, y - 1);if (x >= prm[y])dfs(x / prm[y], y);if (x <= N)dp[y][x] = ans - cnt;
}signed main() {scanf("%lld%lld", &n, &m);for (; prm[inf + 1] <= m; ++inf);dfs(n, inf);printf("%lld\n", ans);return 0;
}