【範例】稀疏表(Sparse Table,ST),倍增法
【題目敘述】https://codeforces.com/contest/474/problem/F


#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
//二維陣列 g[maxn][log2(maxn)]
int g[100005][20]; //2^20 > 1e6
map<int,vector<int> > mp;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, t, l, r;
cin >> n;
for (int i=0; i<n; i++){
//g[i][0]存的資訊為 Ai 的值
cin >> g[i][0]; //the strengths of the ants
mp[g[i][0]].push_back(i); //出現在哪個位置
}
//GCD有結合律才可以用Sparse Table查詢
//將資訊利用二的冪次為單位做N * logN的預處理
//即可使用log N的時間完成對於每個(L, R)區間的詢問
//對於資料不可具有修改操作
for (int i=1; i<20; i++){
for (int j=0; j<n; j++){
if (j + (1 << (i-1)) >= n) break; // index out of boundary
//g[x][i]存的資訊為 Ax ~ A(x+2^i-1)的gcd
//g[2][0]: A2的值; g[2][1] = A2~A3的gcd; g[2][2] = A2~A5的gcd
g[j][i] = __gcd(g[j][i-1], g[j + (1 << (i-1))][i-1]);
}
}
// multiple query
cin >> t;
while (t--){
cin >> l >> r;
l--;
r--;
int len = r - l + 1; //(0,4) len=5
int ans = 0;
int x = l;
int i = 0;
while (len){
if (len & 1){
ans = __gcd(ans, g[x][i]);
x += (1 << i);
}
len >>= 1;
i++;
}
cout << r-l+1-(upper_bound(mp[ans].begin(), mp[ans].end(), r) - lower_bound(mp[ans].begin(), mp[ans].end(), l)) << "\n";
}
return 0;
}