Question on number theory.
I solved 250 Thousand Tons of TNT and I took a look at the solution to see if there was a better way to do it.
I am confused about the first proposal: "Since $$$k$$$ is a divisor of $$$n$$$, there are $$$\mathcal{O}(\sqrt[3]{n})$$$ such $$$k$$$."
I know that you can find the number of divisors of an integer $$$n$$$ in $$$\mathcal{O}(\sqrt[3]{n})$$$ but I don't think that's an upper bound for the amount of divisors itself.
Am I missing something? Have I misunderstood the explanation?
$$$\mathcal O(\sqrt[3]{n})$$$ is a correct upper bound for $$$d(n)$$$. There exists a constant $$$C$$$ such that $$$d(n)\leq C\sqrt[3]{n}$$$ for all $$$n$$$. In fact, $$$d(n)=o(n^{\varepsilon})$$$ for all $$$\varepsilon \gt 0$$$.
I see, thank you.
Denote by $$$d(n)$$$ the number of divisors of $$$n$$$.
Actually, for any $$$\varepsilon \gt 0$$$, $$$d(n) = \mathcal{O}(n^\varepsilon)$$$ (link), so technically the statement is correct. It turns out that for the numbers we deal with in competitive programming, the cube root is a relatively good estimate. To obtain a better estimate, you should look here. The link contains a list of $$$n$$$, which have more divisors, than all smaller numbers.
I have searched something about this; it turns out that the average value of $$$d(n)$$$ is $$$\log n$$$ but it is often exceeded so we use $$$\mathcal{O}(\sqrt[3]{n})$$$ because it's closer to reality (even though, it is not a strict upper bound, it could still be exceeded).
Did I understand correctly?
Edit: fix grammar
yes
For this problem, the key insight is that we only need to consider divisors of n. Since n ≤ 150,000, even with O(√n) divisors (which would be ~387 in worst case), the solution is efficient enough. The O(∛n) mention might be a small error in the explanation, but it doesn't affect the validity of the solution since O(√n) is manageable for this constraints.
As the other comments said $$$\mathcal{O}(\sqrt[3]{n})$$$ is correct, so there is no error in the explanation, it was me.
Your $$$\mathcal{O}(\sqrt{n})$$$ can be exceeded as well, it's still not an upper bound, just a softer approximation.
Simple brute force problem
I don't see how that's relevant to the question.