题目描述

农夫约翰的奶牛们最近成为了一个简单的数字游戏“FizzBuzz”的狂热玩家。

这个游戏的规则很简单：奶牛们站成一圈，依次从一开始报数，每头奶牛在轮到她的时候报一个数。

如果一头奶牛将要报的数字是 3 的倍数，她应当报“Fizz”来代替这个数。

如果一头奶牛将要报的数字是 5 的倍数，她应当报“Buzz”来代替这个数。

如果一头奶牛将要报的数字是 15 的倍数，她应当报“FizzBuzz”来代替这个数。

于是这个游戏的开始部分的记录为：

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16
由于词汇的匮乏，奶牛们玩的 FizzBuzz 中用“Moo”代替了 Fizz、Buzz、FizzBuzz。

于是奶牛版的游戏的开始部分的记录为：

1, 2, Moo, 4, Moo, Moo, 7, 8, Moo, Moo, 11, Moo, 13, 14, Moo, 16
给定 N，请求出这个游戏中第 N 个被报的数。

输入格式
输入一个整数 N。
输出格式
输出游戏中被报出的第 N 个数。
数据范围
1≤N≤109

样例

输入样例：
4
输出样例：
7
样例解释
第 4 个被报的数是 7。

前 4 个被报的数是 1、2、4、7。

注意奶牛说“Moo”时就会跳过一些数字。

算法1

(观察法) $O(1)$

初看，暴力，然后看数据，1e9，想了想，2,3,5的公倍数就是15，那么比如15为一个周期，然后找到里面一共有多少(k)个数，然后找到这些数分别是什么，用n/k可以得到经历了多少个完整的周期，如果到了最后一个周期就结束了，那么其实就是最后一个周期的最后一个数，否则就看余数是多少然后加上哪个数就可以了。

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int a[]={0,1,2,4,7,8,11,13,14};
int main()
{
    long long ans=0;
    long long  n;
    cin>>n;
    ans=n/8*15;
    if(n%8==0)
    {
        cout<<ans-1<<endl;
    }else cout<<ans+a[n%8]<<endl;
    return 0;
}