南京制作网站公司哪家好,自己做编程,网站建设的基本流程有哪些,电商网站的付款功能AtCoder Beginner Contest 300G - P-smooth number解题报告
1 题目链接
传送门
2 题目大意
题目#xff1a;P-光滑数的数量
题目大意#xff1a;
在 1 1 1 到 n n n 中#xff0c;有多少个数的所有质因数均不超过 p ( p ≤ 100 ) p\ (p\leq100) p (p≤100)。
3 解…AtCoder Beginner Contest 300G - P-smooth number解题报告
1 题目链接
传送门
2 题目大意
题目P-光滑数的数量
题目大意
在 1 1 1 到 n n n 中有多少个数的所有质因数均不超过 p ( p ≤ 100 ) p\ (p\leq100) p (p≤100)。
3 解法分析
这道题看着很像搜索于是你可以写出来一份 T L E TLE TLE 代码。 d f s ( x , y ) dfs(x,y) dfs(x,y) 表示在 ( x , p r m [ y ] ) (x, prm[y]) (x,prm[y]) 下单答案。 其中 p r m [ 37 ] prm[37] prm[37] 来存下 100 100 100 内的所有质数因只有 25 25 25 个所以不如打表。
接下来考虑优化。
首先就是一个记忆化搜索然后再剪枝。
十分显然的从大质数向小质数搜可以有效避免无意义的搜索。
于是复杂度玄学起来你也就 A C AC 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;
}
