Pay attention to first exceeds B.
Build 2 arrays, increasing r and corresponding n.

Here is some strictly increasing remainder values r.
i is the array index.
n is the nth prime.
pn is the prime number at nth.

    i -      n(     pn) =             r
    1 -      2(      3) =             2
    2 -      3(      5) =             5
    3 -      5(     11) =           110
    4 -      7(     17) =           238
    5 -      9(     23) =           414
...
95519 - 191037(2617207) =  999966747318
95520 - 191039(2617243) =  999990970954
95521 - 191041(2617253) = 1000005260746

Just note that if is even, the remainder is , otherwise, the remainder is .

This is easy to see since

Also remember to look for and small cases.

I am trying this with C++. My approach is as follow: -> Find all prime below 3000 (Just random number for testing) -> Calculate reminder using formula as per problem description and store the same in vector. -> Loop through all test cases and use upper_bound on vector related to calculated reminder.

I am not getting last two test cases correct. I am able to find issue but do not know what is the solution for the same.

While calculating reminder, I have used data type as long double. For prime number pn = 1223 and n = 200, summation of nth power is going out of limit for double data type. Any idea how to solve this using CPP?

This problem is pretty straightforward with the observations from Problem 120. Unless the input is , we could ignore even number (where the mod is always ).

First begin with prime sieve which is large enough (half a million is more than enough) to satisfy the upper bound. As the odd mods are in increasing order, we could obtain a list of them in sorted order, then use binary search for each test case to find the answer in (I used bisect_right).

And, don't forget that is , as there is no .

Am I the only person solving this question in c++ and getting TLE for 2 & 3 case?