【題解】Codeforces 474F. Ant colony

#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;
}