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.