I was only able to solve PPDIV (Perfect Power Divisors) for 30 pts by finding the contribution of every Perfect Power till sqrt(n).
What was the approach for 100 pts.
2 Likes
My solution might be more complex, hand-wavy than others but here it is:
You can prove that answer for \displaystyle n = n + \sum_{d=2}^{\infty} \sum_{r=2}^{\infty} (-\mu[d])r^d \left \lfloor \frac{n}{r^d} \right \rfloor
Since r^d < n for only finitely many values, this sum only has finitely many non 0 terms.
For d=2, there will be n^{\frac{1}{2}} values of r which will give non 0 terms.
For d=3, there will be n^{\frac{1}{3}} values of r which will give non 0 terms.
and in general,
For d=i, there will be n^{\frac{1}{t}} values of r which will give non 0 terms.
If we can somehow optimise the calculation for d=2 to O(n^{1/3}), we can solve it in the TL.
The calculation for d=2 is \displaystyle \sum_{r=2}^{\infty} r^2 \left \lfloor \frac{n}{r^2} \right \rfloor
For that we can use the harmonic lemma.
Given an r, we calculate the largest r' in O(1) such that \displaystyle \left \lfloor \frac{n}{r^2} \right \rfloor = \left \lfloor \frac{n}{r'^2} \right \rfloor and add
\displaystyle ((r)^2 + (r+1)^2 + \ldots (r')^2) \left \lfloor \frac{n}{r^2} \right \rfloor to our answer.
Also, we know that \left \lfloor \frac{n}{(r' + 1)^2} \right \rfloor \neq \left \lfloor \frac{n}{r'^2} \right \rfloor.
In this way, we can iterate over all distinct values of \left \lfloor \frac{n}{r^2} \right \rfloor
We can prove that there are only O(n^{\frac{1}{3}}) distinct values of \left \lfloor \frac{n}{r^2} \right \rfloor. (Proof by AC)
3 Likes
You have to do things for perfect squares:
- for perfect squares till 10^12, you can simply find the contribution by iterating 10^6 times.
- For perfect squares from 10^12 to 10^18, you cannot simply iterate because it will take 10^9-10^8 iterations. Therefore, you have to find the sum of perfect squares appearing k times.
I have discussed this problem in detail in this video : PPDIV
1 Like
We can prove that there are only O(n^{\frac{1}{3}}) distinct values of \left \lfloor \frac{n}{r^2} \right \rfloor. (Proof by AC)
You don’t have to Proof by AC! :)) You can go over all possible values of \left \lfloor \frac{10^{18}}{r^2} \right \rfloor offline (I left my computer running for several minutes) and actually count the number of distinct values. You’ll get a value that’s approximately 10^6 ish, which means you should be fine.
you can refer the solution here :