[蓝桥杯][2013年第四届真题]幸运数-模拟+dfs

题目描述
幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成
。
首先从1开始写出自然数1,2,3,4,5,6,…
1 就是第一个幸运数。
我们从2这个数开始。把所有序号能被2整除的项删除，变为：
1 _ 3 _ 5 _ 7 _ 9 …
把它们缩紧，重新记序，为：
1 3 5 7 9 … 。这时，3为第2个幸运数，然后把所有能被3整除的序号位置的数删去。注意，是序号位置，不是那个数本身能否被3整除!! 删除的应该是5，11, 17, …
此时7为第3个幸运数，然后再删去序号位置能被7整除的(19,39,…)
最后剩下的序列类似：
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, …
输入
输入两个正整数m n, 用空格分开 (m < n < 1000*1000)
输出
程序输出 位于m和n之间的幸运数的个数（不包含m和n）。
样例输入

30 69

样例输出

8

解题思路：
直接模拟这个过程就行了，一直递归，直到不能删除为止。把不能被n整除的数存放进该数组，知道第n个数比他大了位置就return。

代码如下：

#include <iostream> using namespace std; const int N = 1e6 + 10; int a[N]; int n, m;void dfs(int u) {int cnt = u;if (a[u] >= m)return;for (int i = u; i <= m; i++)//枚举序号 {if (i % a[u])//如果序号不能被整除，就是我们要的。{a[cnt++] = a[i];}}dfs(u + 1); }int main() {cin >> n >> m;for (int i = 1; i <= m; i++)a[i] = 2 * i - 1;if (m > 2)dfs(2);int ans = 0;for (int i = 1; a[i] < m; i++) {if (a[i] > n)ans++;}cout << ans << endl;return 0; }

总结

以上是生活随笔为你收集整理的[蓝桥杯][2013年第四届真题]幸运数-模拟+dfs的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。