This problem is rated 2000, and yet no-one could solve it in official div1 + div2 round, is this a bug or is this task actually not that difficult?

The fastest implementation which i can find is $$$O(p + log_p n)$$$ from here

But from what I have heard there is a faster way of calculating it which might lead to the solution of this problem

Does anyone have a code implementation of it? (Since I can't find it anywhere on the internet)