475D - CGCDSSQ - CodeForces Solution

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//
//                  Solution
//                    Webbly, 27.01.2023
//
//                   llll$lL                       |$$T  ,,,ggg,,,||||||||||||||||||||||||||||llll
//                   $lll$lL                   ,gg@@@@@@@@@@@@@@@@@@@@@@,|||||||||||||||||||||llll
//                $@&$ll|$lg,,,   $*****Ywggg@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@,||||||||||||||||lllll
//                *M$lll|$l$$$$l$l$$$$$$@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@|||||||||||||||llll
//                "*%Wll|$l$glllll||j@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@||||||||||||lllll
//                   llll$lL    ``']@@@@@@@@@@@@@@@@@@@@@@$@@@@@@@@@@$@@@@@@@@@@@@@||||||||||lllll
//                   llll$lL      @@@@@@@@@@@@@@@@$@@@$@@@@@@@@@@@@@@$@@@@@@@@@@@@@@g|||||||||llll
//                   llll$lL    ,@@@@@@@@@@@@@@@@@@@@K$@@@@@@@@@@@@@@$@@@@@@@@@@@@@@@@g||||||lllll
//                   llll$lL    @@@$@@$@@@@@$@@@@@@@M|@@]@@@@@@@@@@@@$@@@@@@@@@@@@@@@@%@||||||llll
//                   llll$lL   @@@@@@@@@@@@@@@@@@@@Ml`@@'%@@@@@@@@@@@$@@|@@@@@@@@@@@@@@$@@g|||llll
//                   llll$lL ,g@@@@@@$@@@@@@@@@@@@MT  $[  $@@@@@@@@@@@@@ ]@@@@@@@@@@@%@@g|M@@||lll
//                   lllll@@@@@@@@@@@@@@@@@@@@@@@@*^"`][  "@@@@@@@@@@@@@  $@@@@@@@@@@@@@@W|||||||l
//                   ll|@@@@@@$@@@@$@@@@@@@@@@@@@`     F   ]@@@@@@@@@U@F   $@@@@@@@@@@@@@@|||||lll
//                   |@@@@@@@@@@@@@@@@@@@@@@@@@@     -~$    ]@@@@@@@K @`   ]@@$@@@@@@@@@@@W||||lll
//                  ,@@@@@@@@O@@@@@@@@@@@@@@@@@C ,gg@@@p '   ]@@@@@@  @-=   @@]@@@@@@@@@@@M||||lll
//                g@@@@@@@@C $@@@@@@@@@@@@@@@@@@P,^"@@@$,    "@@@@  .g@@NB@ -]@@@@@@@@@@@||||llll
//                @@@@@@@@@L  ]@@@@@@@@@@@@@@@$P'$@g@@@@L      ]@@   @$-]@@-$ ]@@@@@@@@@@K|||||lll
//                @@@@@@@N|L   ]@@@@@@@@@@@@@@$% $@@@@%@P       K   '-@@@@@@j $@@@@@@@$@@||||||lll
//                $@@@@@|$lL    ]@@]@@@@@@@@@@*C  *B@@wC             "@$@'@"" $@@@@@@@@@@|||||||ll
//                @@@@M|lllL     '% @@@@@@@@@@                         -`"   ]@@@@@@@$@@@W|||||lll
//                $@@|lllllL      ,L$@@@@@@@@@    .+'|                      -"$@@@@@@@@@@@||||||ll
//                @Mlll&l$l@@&Wggg$w]@@@@@@@@@P   `                    '''   j@@@@P$@@@@@@w|||||ll
//                l$$llll$$$$$$l$$$ll@@@@@@@@@P                              ]@@@@P]@@@@@@@|||||ll
//                *M&Llll$l@@@@wwllll$@@@@@@@@P           -~.=~=~.-          @@@@@F"@@@$@@@|||||ll
//                  'llll$lL          @@@@@@@@L                             g@@@@@L|%@@@$@@@||||ll
//                   llllllL          ]@@@@@@@@W                         ,@@@@@@@@||]@@@$@@@||||ll
//                   llllllL           $@@@@@@@ ,WM,                 ,<||@@@@@@@@@|||]@@@@@@||||ll
//                llllllL            $@@@@@@||L|||lTw,         -^|| ||@@@@@@@@L|||"@@@@@@@|||ll
//                   ll|lllL             $@@@@@@|l||||||||llMww^|       l@@@@@@@@|||||]@@@@@@|||ll
//                   llLlllL         ,,g@@@@@@@@||||l|||||||||||%,|     |@@@@@@@ ||||||$@@@@@W||ll
//                   llllllL    ,gg@@@@@@@@@@@@@@|||||||||l|l]|||%@w,    $@@@]@`  |||||"@@@@@@|||l
//                   llll$lggg@@@@@@@@@@@@@@@@@@%L|||||||||||$A|||@@@@@@@@@@g@Wggggggg,|]@@@@@@||l
//                   llL|@@@@@@@@@@@@@@@@@@@@@@@K *l|||l/|M$@@@@|W]@@@@@@@@ `   ``'''}@L|]@@@@@@|l
//                   lly@@@@@@@@@@@@@@@@@@@@@@@@@P, '*||ll$@@@@@@/ $@@@@@@@@@@@gggggggl$@@$@@@@@@@
//                   l#@@@@@@@@@@@@@@@@@@@@@@@@@@@p\    "$@@@@@F]@p]@@@@@@@@@@@@@@@2|%&%$$$@@@@@@@
//                   ]@@@@@@@@@@@@@@@@@@@@@@@@@@@@@     ,$@]@$$$ ]$$@@@@@@@@@@@@@@@@@@@@@@@$@@@@@@
//
//
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////



#include<bits/stdc++.h>
#include<unistd.h>
//#pragma GCC optimize("O3","Ofast","unroll-loops")
//#pragma GCC optimize("O3", "fast-math")
#define ll long long
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()

using namespace std;

const ll mod = (ll)1e9 + 7, mod3 = 998244353, inf = (ll)1e15, P = 997;

ll binpow (ll a, ll b){
    if (b == 0) return 1;
    if (b & 1) return ((binpow(a, b - 1)) * a);
    else return (binpow(a, b / 2) * binpow(a, b / 2));
}
ll gcd(ll a, ll b){
    return (b ? gcd(b, a % b) : a);
}
ll nums(ll g){
    ll cur = 0;
    while(g){
        cur++, g /= 10;
    }

    return cur;
}
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}

vector <ll> fact(ll n){
    ll i = 2;

    vector <ll> ans;

    ll save = n;

    while(i * i <= save){
        while(n % i == 0){
            ans.pb(i);

            n /= i;
        }

        i++;
    }

    if (n > 1) ans.pb(n);

    return ans;
}

ll get1(ll q, ll g){
    ll cur = 1;

    for (ll i = q; i > g; i--){
        cur *= i;
    }

    return cur;
}
struct T{
    ll mn, mx;
};

ll n, m, k, a[200005], b[200005], sp[200005][24], lg[200005];

map <ll, ll> ans;

string s;

void build(){
    for (ll j = 1; j <= lg[n]; j++){
        for (ll i = 1; i + binpow(2, j) - 1 <= n; i++){
            sp[i][j] = __gcd(sp[i][j - 1], sp[i + (1 << (j - 1))][j - 1]);
        }
    }
}

ll get(ll l, ll r){
    if (r < l) return 0;

    ll d = lg[r - l + 1];

    return __gcd(sp[l][d], sp[r - (1 << d) + 1][d]);
}

void query(){
    cin >> n;

    for (ll i = 1; i <= n; i++){
        cin >> a[i];

        sp[i][0] = a[i];
    }

    build();

    for (ll i = 1; i <= n; i++){
        ll pos = i;

        while(pos >= 1){
            ll l = 1, r = pos, cur = 0, x = get(pos, i);

            while(l <= r){
                ll tm = (l + r) >> 1;

                if (get(tm, i) == x){
                    r = tm - 1;

                    cur = tm;
                }

                else l = tm + 1;
            }

            ans[x] += pos - cur + 1;

            pos = cur - 1;
        }
    }

    cin >> k;

    while(k--){
        ll x;

        cin >> x;

        cout << ans[x] << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    //freopen("mushrooms.in", "r", stdin);
    //freopen("mushrooms.out", "w", stdout);

    for (ll i = 2; i <= 100001; i++){
        lg[i] = lg[i / 2] + 1;
    }

    ll TT = 1;

    //cin >> TT;

    while(TT--){
        //cout << "Case " << cur << ":\n";

        query();

        //cur++;
    }

    return 0;
}

/**


1 2 3
4 2 3
1 5 3
-----
5 5 3

*/