https://codeforces.me/contest/1920/problem/C

Above is the link to the problem i need help with. How is the complexity of inner loop n+logn and not n*logn? GCD is being calculated inside the loop so the logarithmic term should be multiplied right?

Link of the given tutorial:-

https://codeforces.me/blog/entry/122560