Editorial says setters solution is sqrt(n)logn but I don't think it is. Complexity of finding coprime numbers less than m for n is not logn. It's rather 2^k where k is number of distinct prime factors.

Although my solution is actually sqrt(n)log(sqrt(n)), it is different than setter solution and much more complex which uses mobius function, properties of multiplicative and summatory functions and some other things. I don't use the idea of summing over co-prime numbers. Rather I sum over f(i) and find a way to sum them efficiently. I think setter's solution complexity is a lot more than s/he thinks it is