Need help in calculating complexity of given code

Правка en1, от -rynk2200, 2024-06-26 19:03:15

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

Теги algorithm complexity

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский -rynk2200 2024-06-26 19:03:15 375 Initial revision (published)