學步園

題意：一個n個數(1 ≤ n ≤ 10^5)的序列，q個詢問(1 ≤ q ≤ 3 × 10^5)，每個詢問是一個數x，對於每個詢問，輸出gcd(ai, ai+1, ..., aj) == x的(i, j)對數。

題目鏈接：http://codeforces.com/contest/475/problem/D

——>>枚舉一次。。

為什麼不會TLE呢？因為每趟子枚舉基於上一趟的產生的最大公約數個數cnt，yy一下，這個cnt不會很大。。

注意：結果可超32位整數範圍！

#include <cstdio>
#include <map>
#include <algorithm>

using std::map;
using std::swap;

const int MAXN = 100000 + 1;
const int MAXQ = 300000 + 1;

int a[MAXN];
map<int, long long> mpRet;

void Read(int n)
{
    for (int i = 1; i <= n; ++i)
    {
        scanf("%d", a + i);
    }
}

int Gcd(int a, int b)
{
    return a % b == 0 ? b : Gcd(b, a % b);
}

void GetRet(int n)
{
    map<int, int> mpCur;
    map<int, int> mpBuf;

    mpRet.clear();

    for (int i = 1; i <= n; ++i)
    {
        mpBuf.clear();
        for (map<int, int>::const_iterator iter = mpCur.begin(); iter != mpCur.end(); ++iter)
        {
            int nGcd = Gcd(iter->first, a[i]);
            mpBuf[nGcd] += iter->second;
        }
        mpBuf[a[i]]++;
        swap(mpCur, mpBuf);
        for (map<int, int>::const_iterator iter = mpCur.begin(); iter != mpCur.end(); ++iter)
        {
            mpRet[iter->first] += iter->second;
        }
    }
}

int main()
{
    int n, q, x;

    while (scanf("%d", &n) == 1)
    {
        Read(n);
        GetRet(n);
        scanf("%d", &q);
        while (q--)
        {
            scanf("%d", &x);
            printf("%I64d\n", mpRet[x]);
        }
    }

    return 0;
}