Hello everyone, I was trying to solve CSES — Sum of Divisors and finally found a solution within a complexity of O(sqrt(N)), and it worked. However, the problem intrigued my interested so I searched about it on Google, and came across this article explaining a solution to the same problem but with a complexity of O(log2(n))! the observations mentioned in the article are exactly the same I used to build-up my solution, but I don't understand how they consider it as O(log2(n)) or if they are doing something different with the code that I don't get.
In regards of the problem, the main observation is that there are segments of numbers that within each segment, theses numbers will have the same number of occurrences in the total answer. In addition, the number of theses segments is equal to the number of factors of N. In conclusion, the problem is about finding the factorization of the number N (as I guess)
So, what is the most efficient way to find the factorization of a number N? what is the most efficient way to solve the problem? is there anything I am missing with the blog mentioned above?
Thanks in advance!