CF - 475 - D. CGCDSSQ（枚举）

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