L=K+max(a) とおきます。x の値に対応する頂点 1, 2, ⋯,L を考え、
操作を頂点間の移動と捉えれば頂点 1 から頂点 i への最短経路長が求める答えとなります。
ai は全て相異なるため、 ai≥i と考えて良いです。従って辺の数は O(1L+2L+⋯+NL)=O(LlogN) となり、BFS などによって答えが求まります。
なお、操作途中に L より大きい値を経由しないことは、操作2で割り算することに決めた場合に、商が最小となる頂点を目指しても損をしないことから言えます。