kmjp's blog

競技プログラミング参加記です

AtCoder ARC #023 : D - GCD区間

色々頑張ったけど答えはあっさりだった。
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より単純な問題…。