はまやんはまやんはまやん

hamayanhamayan's blog

GCD on Blackboard [AtCoder Beginner Contest 125 C]

https://atcoder.jp/contests/abc125/tasks/abc125_c

解説


追記: GCDの計算をO(1)で計上して書いてありますが、実際はO(log10^9)が最終的な計算量に追加されます。
今回はそんなに問題にならないですが、たまに事前計算とかでこの計算量も削る必要のある問題もあります。

セグメントツリー O(NlogN) : https://atcoder.jp/contests/abc125/submissions/5169320
Sparse Table O(N) : https://atcoder.jp/contests/abc125/submissions/5169346
挟み込み累積和 O(N) : https://atcoder.jp/contests/abc125/submissions/5169357

何から始めようかという感じであるが、考える方針に困ったら、なにかを固定してみるというやり方もある。
ある整数A[i]を書き換えようと決めたとする。
すると、その時実現できる最大公約数の最大値は、A[i]以外の最大公約数となる。
これに気づくのがポイント。

あとは、書き換えようとする対象A[i]を全探索して、A[i]以外の最大公約数の最大値を取れば答え。
書き換え対象の全探索でO(N)かかるので、それ以外の最大公約数をO(logN)かO(1)で求めたい。
これはセグメントツリーを使って、O(logN)でやっても十分間に合うだろう。
ライブラリを持っているなら、それを貼ってやるのが一番バグらないんじゃないかと思う。
GCDのセグメントツリーを作ったことがない人はライブラリ整備としてやってみてもいいかもしれない。
(と言っても、初期値を0にして、マージ関数をgcdに変えるだけ)

int N, A[101010];
SegTree<int, 1 << 17> st;
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, N) st.update(i, A[i]);
 
	int ans = 0;
	rep(i, 0, N) {
		int g = 0;
		g = gcd(g, st.get(0, i));
		g = gcd(g, st.get(i + 1, N));
		chmax(ans, g);
	}
	cout << ans << endl;
}

ちなみにO(1)でやる方法もある。
今回はセグメントツリーでできて、かつ、要素の変更が無いので、SparseTableを使ってもいい。
これでO(1)が達成できる。
 
他にも累積和を使ったO(1)解法もある。
ライブラリに頼らない、かつ、定数倍も最も軽い、一番オススメの解法であるが、
ABCのような比較的早解きが求められるコンテストでは、馴染みのある方法で解くのがいいだろう。
累積和を使った解法をざっくり説明すると、

lft[i] := gcd(A[0], A[1], ..., A[i])
rht[i] ;= gcd(A[i], A[i + 1], ... , A[N-1])

を累積和の要領で作っておく。
すると、A[i]以外の最大公約数は、gcd(lft[i-1], rht[i+1])となる。

f:id:hamayanhamayan:20190428085837p:plain