# PPDIV Approach

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:

1. for perfect squares till 10^12, you can simply find the contribution by iterating 10^6 times.
2. 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 :