Need help in calculating complexity of given code

Revision en1, by -rynk2200, 2024-06-26 19:03:15

https://codeforces.net/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.net/blog/entry/122560

Tags algorithm complexity

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English -rynk2200 2024-06-26 19:03:15 375 Initial revision (published)