Codeforces Round #729 Strange Function 题解 (Java/C++)

题解

首先我们立刻可以注意到,当i为奇数时,f(i)=2。接着我们开始考量f(i)=3的情况。显然根据定义我们可以知道,只有i为偶数,且i不能被3整除时f(i)=3。
因此我们也可以说:对于所有的i,排除f(i)=2和f(i)=3的情况,剩下的i一定不能被6整除。进一步,当我们考虑到f(i)=4的情况后,剩下的i一定不能被lcm(4,6)=12整除。

根据上图我们可以发现,2之后剩下的i都满足$i\equiv 0 (mod 2)$。
3之后剩下的i都满足$i\equiv 0 (mod 6)$,也就是6和12。(lcm(2,3)=6)
4之后剩下的i都满足$i\equiv 0 (mod 12)$,也就12和24。(lcm(6,4)=12)

于是,我们只需要依次枚举,每次比较上一次剩下的数目和这次剩下的数目即可。

综上,满足$f(i)=x$的i的个数为$\frac{n}{lcm(1,2,3,...x-1)}-\frac{n}{lcm(1,2,3,...,x)}$。

代码

Java

Submission #121283456 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #121283575 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论