题解 P5834 【[USACO19DEC]MooBuzz】
rui_er
2019-12-19 21:48:40
**题目大意:求从一开始第$n$个既不是三的倍数又不是五的倍数的数**
没有思路。列几个数看看:
1, 2, 4, 7, 8, 11, 13, 14, 16, 17, 19, 22, 23, 26, 28, 29, ……
因为三乘五等于十五,所以猜测模15的余数可能有规律。列一下:
1, 2, 4, 7, 8, 11, 13, 14, 1, 2, 4, 7, 8, 11, 13, 14, ……
于是很明显地发现存在8位的循环节。根据数学推导可得(以下所有公式中的除号“/”均表示整除,即向下取整):
$ans=(n/8)*15+a[n\mod8]$,其中$a[1...n]=\{14, 1, 2, 4, 7, 8, 11, 13\}$,就是上面推导的余数。
但是当$n\mod8=0$时发现有问题,此时$ans=(n/8)*15-1$,特判一下就好。
AC代码:
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[8] = {14, 1, 2, 4, 7, 8, 11, 13};
int main()
{
int n;
cin>>n;
int d = n / 8;
int ans = d * 15;
if(n % 8 != 0) ans += a[n%8];
else --ans;
cout<<ans<<endl;
return 0;
}
```