USACO analysis
zys |
19 Nov 2020
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
题目大意
有一排的头牛，每头牛都有自己的编号。现在，如果编号是 3 的倍数，这头牛的编号会变成 Fizz；如果是 5 的倍数，这头牛的编号会变成 Buzz；如果是15 的倍数，这头牛的编号会变成 FizzBuzz。找出第 N 头有编号的牛所对应的编号。（1 ≤ N ≤ 109）
思路
根据计算，因为每 15 头牛之间就会出现 8 头有编号的牛，所以，后面的牛的编号就可以根据周期来算。因为每 15 头牛为一个周期，每个周期里有8 头有编号（第一个周期中 8 个编号分别是：1，2，4，7，8，11，13，14）。所以 N % 8 就是对应当前这个周期所对应的索引。因为是 15 头牛为一个周期，所以，N / 8 即比第一个周期多了几个 15。所以，要找到第 N 头有编号的牛所对应的编号就是 N % 8 索引所对应的编号再加上 15 * (N / 8)。特殊情况：当 N 为 8 的倍数时，因为 N 可以整除 8，所以 N / 8 会比不是 8 的倍数时多算了一个 1。因此，如果 N 为 8 的倍数，那么 N / 8 要减 1。
第一个周期的 8 个编号可以用一个长度为 8 的数组 iD 储存。第 N 头有编号的牛所对应的编号 Cow(N) = iD[N % 8] + 15 * (N / 8)；如果 N 为 8 的倍数，Cow(N) = iD[N % 8] + 15 * (N / 8 - 1)。
复杂度
每次找到第 N 头牛就是查找 N 的索引所对应的编号，然后对这个编号做加法。因为查找一个数组 index 位置的元素是 O(1)，所以复杂度是 O(1)。
