• 求解子數組的&,|,lcm,gcd的最值or計數問題，如果采用暴力的做法，那么時間復雜度會來到o(n^2),其實在求解的過程中，會出現很多的結果不變的情況，所以我們就可以提前結束

• 存在一定的單調性，一般都是 枚舉右端點,r然后讓區間一直加入右端點，如果更新的值與原本的區間的值相同，就可以停止更新

gcd的問題

最大公約數

• 首先，這個數據范圍比較大，是需要使用nlogn的算法進行求解的
• 接著，查看問題的思路，可以發現，如果原始的數組中存在1，那么就只需使用n-1的數量即可，否則的話，就得想辦法，是否可以最少代價gcd出一個1,那么這里就是可以轉化為一個gcd子數組為1的最短長度的問題，由于得使用nlogn算法，所以就是考慮要么使用線段樹或者LogTrick算法，那么這里就使用簡單的Logtrick算法進行求解

import os
import sys
import math
from collections import Counter# 請在此輸入您的代碼# 先判斷是否包含這個 1,如果包含1的話，那么結果就是總的數組長度減去1的數量
# 否則就是找到區間gcd為1的最短的
n = int(input())
a = list(map(int,input().split()))b = a[::]
minlen = n+1
for i in range(n):if b[i] == 1:minlen = 1breakfor j in range(i-1,-1,-1):if math.gcd(b[j],b[i]) == b[j]:breakb[j] = math.gcd(b[j],b[i])if b[j] == 1:minlen = min(minlen,i-j+1)if minlen == 1:cou = Counter(a)print(n-cou[1])
elif minlen != n+1:# minlen-1次的操作會帶來一個1，n-1print(minlen-1+n-1)
else:print(-1)

• 如果使用線段樹的話，就得使用線段樹+二分