2019年4月27日土曜日

ABC 125 C - GCD on Blackboard

ABC 125 C - GCD on Blackboard

危うく平方分割するところだった……

AiA_iを書き換えるとき、最大公約数は高々gcd⁡(A1,...,Ai−1,Ai+1,...,AN)\gcd(A_1, ..., A_{i-1}, A_{i+1}, ..., A_N)であり、実際、AiA_iをgcd⁡(A1,...,Ai−1,Ai+1,...,AN)\gcd(A_1, ..., A_{i-1}, A_{i+1}, ..., A_N)に書き換えればこの値にできる。したがって、G(i):=gcd⁡(A1,...,Ai−1,Ai+1,...,AN)G(i) := \gcd(A_1, ..., A_{i-1}, A_{i+1}, ..., A_N)とすると、G(i)G(i)の最大値が答えである。

L(i):=gcd⁡(A1,...,Ai−1)L(i) := \gcd(A_1, ..., A_{i-1}), R(i)=gcd⁡(Ai+1,...,AN)R(i) = \gcd(A_{i+1}, ..., A_N)とするとG(i)G(i)は

G(i)=gcd⁡(L(i),R(i))G(i) = \gcd(L(i), R(i))
で計算できるので、

L(i):=gcd⁡(L(i−1),Ai−1)R(i):=gcd⁡(R(i+1),Ai+1) \begin{aligned} L(i) := \gcd(L(i-1), A_{i-1}) \\ R(i) := \gcd(R(i+1), A_{i+1}) \end{aligned}

を利用して先にL(i)L(i), R(i)R(i)のテーブルを作っておけばよい。

あと、今まで意識したことがなかったけど、gcdの単位元として00が使えるという理解を得た。

別解とか

これはうまい考え方だと思った。……けど、最初の2つの数の約数から素朴に調べる方針だと、例えば

100000
735134400 698377680 735134400 ... (99996個連続) ... 735134400 1 1

みたいな入力でけっこう時間が怪しい。とはいっても、高々2×1082 \times 10^8程度のループですむので、C++なら大丈夫だろうな。1

Divisor function d(n)d(n)の上限を見る限り、計算量は任意のϵ>0\epsilon > 0に対してo(N(max⁡Ai)ϵ){\mathcal o}(N(\max A_i)^\epsilon)と評価できるようだが、漸近的な評価があまり役に立たない例にも見える。sup⁡i≤nd(i)\sup_{i \le n} d(i)の具体的な値を覚えておいたほうが良さそう。

参考: https://gist.github.com/dario2994/fb4713f252ca86c1254d

  1. jupiroさんの提出コードは735134400 ... (99998個連続) ... 735134400 1 1で（コードテストでは）2600msだったが、これは改善可能で、前処理で約数の重複を除くくらいで十分なはず。 ↩︎

投稿者