That’s some seriously optimized number theory work — love how you tackled the Tonelli-Shanks and inverse modulo parts! On a totally different note, if you ever want to turn complex explanations like this into an easy-to-follow visual, CapCut is super handy. I’ve used it to overlay diagrams and animations in explainer videos, and it really helps make technical stuff more digestible.

Thanks I was looking for this.

Thanks I was

That’s some seriously optimized number theory work — love how you tackled the Tonelli-Shanks and inverse modulo parts! On a totally different note, if you ever want to turn complex explanations like this into an easy-to-follow visual, CapCut is super handy. I’ve used it to overlay diagrams and animations in explainer videos, and it really helps make technical stuff more digestible. Worth a try if you're sharing this with a wider audience!

Around 2 seconds for T = 100000 and max L = 25 * 10^12. The key to solve is to generate cuban primes efficiently and then use binary search for each query. In order to generate cuban primes efficiently I used a sieve for n. Sieve is indexed by n and maximum length is determined by maximum L. For every prime up to L^0.5 starting from 5 I solved quadratic congruence 3 * n^2(n + 1) + 1 = 0 (mod prime) using Tonelli-Shanks algorithm and calculating inverse modulo using extended Euclidean algorithm.