Chatgpt can write a solution for this problem if we go up to 10^10. 10^16 is too hard!
I don’t understand this problem (I didn’t tackle it myself) but wanted to see how quickly chatgpt could solve it and how far along it would go.
First it made a naive solution that would work until 10^6. Then we used that output to verify improved versions.
And we managed to improve it until 10^10 only. (Staying within a minute timeout.)
It did a DP approach (it suggested itself). I suggested to try numba and numpy. And with that it managed until 10^10. I think it’s still brute forcing it and one might leverage much better techniques in order to reach 10^16.
replies(1):