学步园

题意：一个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;
}