A way to solve 1547F(#731F) by implementation

Revision en12, by handsome_gay, 2021-07-10 23:37:23

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.

solution

#### History

Revisions

Rev. Lang. By When Δ Comment
en12 handsome_gay 2021-07-10 23:37:23 50
en11 handsome_gay 2021-07-10 23:35:28 1 Tiny change: 'q a_{i+1}$, then we ' -> 'q a_{i+1}$), then we '
en10 handsome_gay 2021-07-10 23:31:33 7 Tiny change: ' y$, then$gcd(x,y)' -> ' y$, then either$gcd(x,y)'
en9 handsome_gay 2021-07-10 23:31:10 16 Tiny change: ' $gcd(x,y)' -> '$gcd(x,y)=x$or$gcd(x,y)'
en8 handsome_gay 2021-07-10 23:28:57 6 Tiny change: ' 1$and$x>y$, then$' -> ' 1$and$x\neq y$, then$'
en7 handsome_gay 2021-07-10 23:25:20 6 Tiny change: ' 1$and$x\neq y$, then$' -> ' 1$and$x>y$, then$'
en6 handsome_gay 2021-07-10 23:19:16 7 Tiny change: 'now, if $x!=1$ and $x\' -> 'now, if$x\neq 1$and$x\'
en5 handsome_gay 2021-07-10 23:18:54 29
en4 handsome_gay 2021-07-10 20:31:28 11
en3 handsome_gay 2021-07-10 20:30:02 12
en2 handsome_gay 2021-07-10 20:29:06 48 Tiny change: '$too.\n\n\n~~~~' -> '$ too.\n\n[submission:1010182]\n\n\n~~~~'
en1 handsome_gay 2021-07-10 20:24:23 2399 Initial revision (published)