题解 P5834 【[USACO19DEC]MooBuzz】
2017gdgzoi999
2019-12-27 21:12:23
### 简要解法：
我们将所有 $3$ 的倍数和 $5$ 的倍数去除，剩余的列表（报出的数）前段如下：
`1 2 4 7 8 11 13 14/`
`16 17 19 22 23 26 28 29/`
`31 32 34 37 38 41 43 44...`
设第 $i$ 个列表中的数为 $f_i$。
上面，`/`符号将列表分成了若干部分，其中每一个部分有 $8$ 个数。
对于每部分的最后一个数找规律，易得如下公式（$k$ 为正整数）：
$$f_{8k} = 15k-1$$
得到这个公式后，对于 $N$ 为 $8$ 的倍数的情况，可以直接套用公式求解。
如果不是呢？不妨设 $N=8k+a$（$1 \leq a \leq 7$），问题就转化为从 $15k$ 开始的被报出的第 $a$ 个数。由于 $a$ 很小，这一部分只要暴力即可。
代码（文言）：
注释中也有一些对于文言语句的说明。
```cpp
注曰。「「注曰语句是程序中的注释。」」。
注曰。「「注释中说明的语句是简体字。实际编程中需要使用繁体。」」。
吾嘗觀「「算經」」之書。方悟「取底」之義。
注曰。「「吾尝观...之义语句导入库中函数。」」。
吾有一術。名之曰「判断合法」。欲行是術。必先得一數。曰「甲」。是術曰。
注曰。「「判断是否会被报出。吾有一术名之曰语句声明函数」」。
注曰。「「欲行其术必先得...曰语句声明参数。无参时可省略。曰可以有多个。」」。
注曰。「「是术曰语句声明函数开始」」。
除「甲」以三。所餘幾何。名之曰「除三之余」。
若「除三之余」等於零者。乃得陰也。
注曰。「「若...乃语句表示满足某个条件时的返回值。」」。
注曰。「「三的倍数不会被报出」」。
除「甲」以五。所餘幾何。名之曰「除五之余」。
若「除五之余」等於零者。乃得陰也。
注曰。「「五的倍数不会被报出」」。
乃得陽也。
注曰。「「如果不是三的倍数也不是五的倍数，它就会被报出」」。
注曰。「「返回布尔值。阳表示真，阴表示假。」」。
是謂「判断合法」之術也。
注曰。「「是谓...之术也语句声明函数结束。」」。
施「require('fs').readFileSync」於「「/dev/stdin」」。名之曰「初始输入」。
施「(buf => buf.toString().trim())」於「初始输入」。昔之「初始输入」者。今其是矣。
施「parseInt」於「初始输入」。名之曰「甲」。
注曰。「「输入部分。使用Javascript的语法。」」。
注曰。「「parseInt函数将字符串转换为数字」」。
除「甲」以八。名之曰「周期数」。
注曰。「「计算此数之前的完整周期次数。」」。
注曰。「「加/乘/除...以语句进行运算。」」。
注曰。「「名之曰语句声明变量。其值在前面语句提到。」」。
施「取底」於「周期数」。昔之「周期数」者。今其是矣。
注曰。「「此语言除法不会向下取整，需要使用函数。」」。
注曰。「「施...于语句执行函数。于传入参数，可以有多个。」」。
注曰。「「昔之..者斤其是矣语句将变量重新复值。其值在前面语句提到。」」。
乘「周期数」以十五。名之曰「结果」。
加「结果」以负一。昔之「结果」者。今其是矣。
注曰。「「现在的结果是上文中15k-1的值。」」。
除「甲」以八。所餘幾何。名之曰「剩余」。
注曰。「「往后剩余要找的数字数量即为N除8的余数。」」。
注曰。「「除...以...所余几何语句计算余数。」」。
恆為是。
注曰。「「恒为是语句表明一个死循环。」」。
若「剩余」小於一者。乃止。云云。
注曰。「「现在已经是目标，退出循环并输出它」」。
注曰。「「乃止语句表明退出循环，相当于break。」」。
注曰。「「若...云云语句表明若满足条件会执行的语句。相当于if。」」。
加「结果」以一。昔之「结果」者。今其是矣。
施「判断合法」於「结果」。名之曰「是否合法」。
注曰。「「将当前数增加一，然后检查是否会被报出」」。
若「是否合法」等於陽者。
加「剩余」以负一。昔之「剩余」者。今其是矣。
注曰。「「次数会被报出。找的数的剩余数量减一。」」。
云云。
云云。
注曰。「「此处的云云语句说明循环结束。」」。
加「结果」以零。書之。
注曰。「「将最终的结果输出。」」。
注曰。「「书之语句进行输出。调用此语句将在最后额外输出一个换行符。」」。
```
附：同义C++代码。
```cpp
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
bool check(ll x) {
if (x%3==0) return false;
if (x%5==0) return false;
return true;
}
int main() {
ll k; scanf("%lld",&k);
ll res=15LL*(k/8)-1; k&=7;
while (k) {
if (check(++res)) --k;
}
printf("%d", res);
return 0;
}
```