https://www.spoj.com/problems/MATH1/ I need help, the tl is 20s, I assume the solution is n^3 with some dp, but don't know how to

Hello everyone, i need help with this spoj problem please https://www.spoj.com/problems/DIVCNT2/ I looked online but i only found chinese blogs and when i tried to translate it, it wouldnt translate correctly ofc and i dont understand it. It would be great if someone can explain the solution