まず、 \(A\) の要素がすべてある値の倍数である場合は、すべての要素をその値で割ってしまっても問題は変わりません。以下、 \( \gcd(A_1,A_2,\ldots,A_N)=1\) を満たすとします。

ここで、ある奇素数 \(p\) について、 \(\sum_{i=1}^N A_i \equiv 0 \pmod p\) を満たすとします。この時、操作終了後の \(A_i \bmod p\) はすべて \(0\) になっていなければなりません。

\(\gcd(A_1,A_2,\ldots,A_N)=1\) より、操作前の \(A\) には \(0\) でない要素が必ず \(1\) つは存在します。操作によって、要素は \(x \to x-y, y \to 2y\) のように変化しますが、 \((x \bmod p, y \bmod p) \neq (0,0)\) の場合は \((x \bmod p,y \bmod p) = (0,0)\) とすることができませんから、 \(\sum_{i=1}^N A_i\) が奇素数を約数に含む場合(すなわち \(2\) べきではない場合)は条件を満たすことが不可能です。

逆に、 \(\sum_{i=1}^N A_i\) が \(2\) べきである場合は可能です。以下のような操作を行い、すべての要素を偶数にすることで、 \(2\) 倍サイズの小さい問題に帰着します。 \(\sum_{i=1}^N A_i = 1\) まで小さくすれば条件は達成されます。

• 奇数である要素を \(2\) つ選ぶ。操作を行う。

操作回数は \(N/2 \times \lceil \log_2 \max(A) \rceil\) で抑えられます。よって、この問題を解くことができました。計算量は \(O(N\log \max(A))\) です。