CFR 798 C. Mike and gcd problem ( Math )

Problem - C - Codeforces

題意：
給長度為 N 的數列 A。每次可以進行的操作為，選擇一個 i，並執行 A[ i ], A[ i + 1 ] = A[ i ] - A[ i + 1 ], A[ i ] + A[ i + 1 ]。問至少要進行幾次操作，才能使得 gcd( A ) > 1。

制約：
The first line contains a single integer n (2 ≤ n ≤ 100 000) — length of sequence A.
The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 1e9) — elements of sequence A.

解法：
若原始的 gcd( A ) > 1，直接輸出 0。
注意到對於 ( a, b )：
一次操作：( a - b, a + b )
二次操作：( -2 * b, 2 * a )
三次操作：( -2 * ( a + b ), 2 * ( a - b ) )
四次操作：( -4 * a, -4 * b )
....
觀察到 gcd( a - b, a + b ) = 2 * gcd( a, b )
證明：
d = gcd( a - b, a + b )
d | a - b and d | a + b
=> d | ( a - b ) + ( a + b ) and d | ( a - b ) - ( a + b )
=> d | gcd( 2 * a, 2 * b )
所以只在意數列的奇偶性，依序獨立處理即可。

時間 / 空間複雜度：
O( N lg max_A )

from functools import reduce

N = int( input() )
A = list( map( int, input().split() ) )

def gcd( a,b ):
  if b == 0: return a
  return gcd( b, a % b )

print( "YES" )
if reduce( gcd, A ) > 1:
  print( 0 )
else:
  ans = 0
  for i in range( N - 1 ):
    while A[ i ] & 1:
      ans += 1
      A[ i ], A[ i + 1 ] = A[ i ] - A[ i + 1 ], A[ i ] + A[ i + 1 ]
  if A[ N - 1 ] & 1:
    ans += 2
  print( ans )