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

Solution:

First, we can note that: when i is odd number, f(i)=2.
Then we consider the case that f(i)=3. Based on the definition, if and only if i is even number and i cannot be divisible by 3, then f(i)=3.
So, we know that: for all the i, after excluded f(i)=2 and f(i)=3, the remain i cannot be divisible by 6.
Furthermore, after we excluded f(i)=4, the remain i cannot be divisible by lcm(4,6)=12.

Based on the image above we can find that:
after f(i)=2, all the i remain match $i\equiv 0 (mod 2)$.
after f(i)=3, all the i remain match $i\equiv 0 (mod 6)$, which is 6 and 12. (where lcm(2,3)=6)
after f(i)=4, all the i remain match $i\equiv 0 (mod 12)$, which is 12 and 24. (where lcm(6,4)=12)

So, we just enumerate the value of f(i), we compare the number of remain i between two value every time.

So, the number of i where $f(i)=x$ is $\frac{n}{lcm(1,2,3,...x-1)}-\frac{n}{lcm(1,2,3,...,x)}$.

Code:

Java

C++