I coded up the solution in Java, and for some reason, I am getting TLE. I feel the solution is correct. Any insights will be appreciated. Code : https://github.com/aizenkhan/Misc.-Solutions/blob/master/BFS/SPOJ_AKBAR.java

Problem link : http://acm.timus.ru/problem.aspx?space=1&num=1673 I know i need to calculate the inverse Phi function or i can also precompute the Euler's Totient function and proceed from there but the problem is, with such a large constraint, both don't seem to be working for me. It would be great if someone could point me in the right direction, because i have already spent a ton of time on this problem, so any help would be appreciated.