why are we using the GCD logic in this problem?

i am not able to figure out why are we using the GCD logic in this problem.

someone plz explain it to me

You can use the problem code EGRCAKE to search the discussion forum for the editorial. It’s here: https://discuss.codechef.com/questions/76886/egrcake-editorial