I’m making this thread in the same spirit as the ones made for previous month’s long challenges by @vijju123 and @aryanc403.
I would request you all to NOT ask other people to review your code as an answer in this thread but in the end it’s your choice.
Anyway, here’s my 2 cents on the problems I found interesting.
The most efficient solution is to do a binary search where, at each step you query for a point that divides the current range in a ratio 1:r\ such that r satisfies r^{c+1} = (r+1)^c.
I was able to show that given sum can be written as \displaystyle \sum_{n=1}^N \Big(f*h(n)\Big)\Big(n^p\Big)
Where * represents Dirichlet Convolution and h(n) counts the number of ways to chose m numbers such that their gcd is 1 and their lcm is n.
h can be written in terms of other common functions related to Dirichlet Convolution as h = \mu * \mu * d^m. Their meaning can be found in the wiki I linked.
And the whole sum written in terms of common functions is \displaystyle \sum_{n=1}^N (f*\mu *\mu *d^m)\cdot(Id_p)(n)\ where \cdot represents pointwise multiplication.
My guess is that we can somehow calculate prefix sums of h\cdot Id_p efficiently and using them we can calcalate the required sum in O(n^{\frac{3}{4}}) using the method shown here.