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.
[SPOILER]
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!
No, you cannot factor a number in
O(number length), or even in any polynomial of number length. At least, no one knows how to do that. The quickest known algorithm is general number field sieve but it has a large constant and it's still superpolynomial.The article you linked to is wrong, their method is not $$$\mathcal{O}(\log n)$$$ but $$$\mathcal{O}(\sqrt{n})$$$. You can either use your brain to verify that or just try their algorithm on something like $$$10^{16}$$$ -- it takes it about 20 seconds.
Classic geeksforgeeks...
The article is littered with examples of trivialities, but the magic line
i = n / (n / (i + 1));which the complexity depends on is just completely unexplained. (It seems to go through all numbers of the form $$$\left \lfloor \frac{n}{i} \right \rfloor$$$, which is bounded below by $$$\sqrt{n}$$$.)And don't you hate how GeeksForGeeks links come up as the first results for all the algorithm related google searches?
The more frustrating thing is that they try to be the C++ reference and have a (pretty useless, much worse than either of the real references) page for just about every function in C++.
All things considered I pretty strongly suspect that they use some sketchy techniques that manipulate the Google algorithm to show them on the top.
It's not known if integer factorization is in P. Sum of divisors is a bit easier problem but I haven't heard about the polynomial algorithm that solves it (maybe they are equivalent).
yes but only if p=np
Factorization is not known to be NP-complete. It may be in P even if P != NP.
interesting
btw how to solve this problem https://codeforces.net/contest/993/problem/E?
substitute (numbers what >= k) with 0, and (numbers that < k) with 1.
Now we need to count number of segments with fixed sum.
Make prefix sum array (PS) of new array.
Now we need to count number of pairs
This is trivial task for FFT.
Also take care about (L > R) and (L = R) cases
No. Take any large prime.
You are completely right! I am a bit confused, how can we prove that the complexity of the solution is O(sqrt(N)) now?