USACO analysis
Jczeng |
17 Nov 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
Problem 1. MooBuzz
题目大意：
- 类似丑数，给定一个n，找到第n个因数不是3或5的数
思路N.1：
- 找出3，5倍数出现的规律：每15为一组，每组内的有效数字有8个，将那八个数添加进名为sample的数组；
- 用8整除n，得到的数为输出值所在的组，用group表示；
- 再用8对n求余再减1，得到的数为输出值所在组内，它的详细位置，用loc表示；
- 最后group*15+sample[loc]便是输出辽。
复杂度分析N.1:
- n的区间为1到10^9，该方法将循环n/15次，虽然有些暴力，但复杂度刚好少于10^8，而且思路直接，循环简单，若时间比较紧凑，可优先这个方法。
思路N.2:
- 思路有点类似动态规划里的重叠子问题，单一变量不断往下传递直到达到某个值；
- 找出n之前所有3，5，15的倍数（包括它们自己）；
- 分别记录其数量，并相加得到一个和，用sum表示；
- 将sum和n相加，继续找其之前的3，5，15的倍数；
- 得到新的sum需要减去上一次得到的sum；
- 不断执行，直到sum为0，此时的n便是输出。
复杂度分析：
- 此方法的最差时间复杂度为 (n%8) * [15 * (n//15+1)]
