Bayan 2015 Contest Warmup : D. CGCDSSQ

せっかくのチャンスをしょうもないミスで潰した。
http://codeforces.com/contest/475/problem/D

問題

N要素の数列A[i]が与えられる。
ここでQ個のクエリX[i]に答えよ。

各クエリでは、GCD(A[L], A[L+1], ... , A[R])となるような(L,R)の対の数を答えよ。

解法

実はこの問題は既出である。
AtCoder ARC #023 : D - GCD区間 - kmjp's blog

そのためか、日本人の正答者が多かったようだ。

int N;
int A[100050];
int Q;
int X[400050];
map<int,ll> QQ;
map<int,ll> G;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	cin>>Q;
	FOR(i,Q) cin>>X[i], QQ[X[i]]=0;
	FOR(i,N) {
		map<int,ll> G2;
		G2[A[i]]=1;
		ITR(it,G) G2[__gcd(it->first,A[i])]+=it->second;
		swap(G,G2);
		ITR(it,G) if(QQ.count(it->first)) QQ[it->first]+=it->second;
	}
	FOR(i,Q) _P("%lld\n",QQ[X[i]]);
	
}

まとめ

せっかくのチャンスを配列数のミスでつぶした。
これが解けていればかなり上位に入ったのに…。