Please subscribe to the official Codeforces channel in Telegram via the link ×

handsome_gay's blog

By handsome_gay, history, 3 years ago, In English

As we know, if $$$x\neq 1$$$ and $$$x\neq y$$$, then either $$$gcd(x,y)=x$$$ or $$$gcd(x,y)<=\frac{x}{2}$$$. That means for each element $$$a_i$$$ in the array, it will change at most $$$log(a_i)$$$ times before it becomes $$$1$$$.

So we can implement the process, but for every round we only consider the element that will change, then we just do $$$O(N*log(a_i))$$$ times change.

How to find the elements that will change in the next round? We can see that elements will change in the next round, are only in the elements change in this round and their left element, so we just check them. The number of elements we check is $$$O(N*log(a_i))$$$ too.


Full text and comments »

  • Vote: I like it
  • +45
  • Vote: I do not like it