色々頑張ったけど答えはあっさりだった。
http://arc023.contest.atcoder.jp/tasks/arc023_4
問題
N要素の正の整数列A[i]及びM個のクエリX[i]が与えられる。
各クエリX[i]において、A[i]の連続した部分列A[s]~A[t]の最大公約数がX[i]となる区間(s,t)の組み合わせ数を答えよ。
解法
クエリ云々は置いておいて、部分列の最大公約数の数を列挙しよう。
自分は本番BitIndexTreeでガリガリ計算したが、一部TLEがとりきれなかった。
実際はもっと単純な解法がある。
各iについて、区間(A[0],A[i-1])、(A[1],A[i-1])、(A[2],A[i-1])、…、(A[i-1],A[i-1])における最大公約数とその登場回数を覚えておき、それぞれとA[i]の最大公約数を求めることで(A[0],A[i])、(A[1],A[i])、…、(A[i-1],A[i])を求めればよい。(ついでに(A[i],A[i])も追加する)
(A[0],A[i-1])、(A[1],A[i-1])、(A[2],A[i-1])、…、(A[i-1],A[i-1])は一見i通りありそうなので、全体でO(N^2)かかりそうだが、そもそもA[i-1]の約数は数十個程度にしかならないので、(A[0],A[i-1])、(A[1],A[i-1])、(A[2],A[i-1])、…、(A[i-1],A[i-1])の最大公約数も数十通りしか登場しないため、高速に処理できる。
void solve() { int f,i,j,k,l,x,y; int N,M; map<int,ll> MM,M2,C; cin>>N>>M; FOR(i,N) { cin>>x; M2.clear(); ITR(it,MM) { C[__gcd(it->first,x)] += it->second; M2[__gcd(it->first,x)] += it->second; } M2[x]++; C[x]++; swap(MM,M2); } FOR(i,M) { cin>>x; _P("%lld\n",C[x]); } }
まとめ
終わってみるとCより単純な問題…。