Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 254 F問題 Rectangle GCD

AtCoder ABC ABC254 F問題 500 pts

問題

atcoder.jp

提出解答

atcoder.jp

問題の概要

長さが N の整数列 A=(A_i)_{i=1}^N, B=(B_j)_{j=1}^N と2重添字数列 X=(X_{i,j})_{1 \leq i,j \leq N} がある. ここで, X_{i,j}=A_i+B_j である.

次の Q 個の質問に答えよ.

  • h_1 \leq i \leq h_2, w_1 \leq j \leq w_2 における全ての X_{i,j} の最大公約数求めよ.

制約

  • 1 \leq N,Q \leq 2 \times 10^5
  • 1 \leq A_i, B_j \leq 10^9
  • 1 \leq h_1 \leq h_2 \leq N
  • 1 \leq w_1 \leq w_2 \leq N

解法

x_1, \dots, x_k に対する最大公約数を \gcd(x_1, \dots, x_k) と書くことにする. このとき, 次が成り立つ.

x,y,z を整数とするとき, 以下が成り立つ.

  • \gcd(x,y,z)=\gcd(\gcd(x,y),z)=\gcd(x,\gcd(y,z))
  • \gcd(x,y)=\gcd(y,x)
  • \gcd(x,x)=x

そして, 次のことも成り立つ. この性質がこの問題の本質である.

整数 x,y,a に対して, \gcd(x,y)=\gcd(x,y+ax)

証明
g:=\gcd(x,y), h:=\gcd(x,y+ax) とする. g=\gcd(x,y) より, x=gp, y=gq となる整数 p,q が存在するが, x=gp, y+ax=g(q+ap) とより, x,y+ax は共に g の倍数なので, g \leq h である.

同様に, h=\gcd(x,y+ax) なので, x=hr, y+ax=hs となる整数 r,s が存在するが, x=hr, y=h(s-ar) より, x,y はともに h の倍数なので, h \leq g である.

以上から, g \leq h かつ h \leq g なので, g=h である.

この性質において, 正の整数 x,y に対して a:=\lfloor \frac{x}{y} \rfloor とすると, まさしく Euclid の互除法が整合性を持つための主張になる.

この性質を利用すると, 次のことが示せる.

k \geq 2 とする. 整数 x_1, \dots, x_k に対して,

\gcd(x_1, \dots, x_k)=\gcd(x_1, x_2-x_1, \dots, x_k-x_{k-1})
が成り立つ.

証明

\begin{align} \gcd(x_1, \dots, x_k) &=\gcd(\gcd(x_1, \dots, x_{k-2}), \gcd(x_{k-1}, x_k)) \\ &=\gcd(\gcd(x_1, \dots, x_{k-2}), \gcd(x_{k-1}, x_k-x_{k-1})) \\ &=\gcd(\gcd(x_1, \dots, x_{k-2}), x_{k-1}, x_k-x_{k-1}) \\ &=\gcd(\gcd(x_1, \dots, x_{k-3}), \gcd(x_{k-2}, x_{k-1}), x_k-x_{k-1}) \\ &=\gcd(\gcd(x_1, \dots, x_{k-3}), \gcd(x_{k-2}, x_{k-1}-x_{k-2}), x_k-x_{k-1}) \\ &=\gcd(\gcd(x_1, \dots, x_{k-3}), x_{k-2}, x_{k-1}-x_{k-2}, x_k-x_{k-1}) \\ &=\vdots \\ &=\gcd(x_1, x_2-x_1, \dots, x_{k-1}-x_{k-2}, x_k-x_{k-1}) \\ \end{align}

となる.

これらの性質から, 各質問に対して, 最大公約数を以下のようにして求めることができる. ただし, C_i:=A_{i+1}-A_i, D_j:=B_{j+1}-B_j とする. また, 以降では x,y の最大公約数を x \wedge y と書くことにする.

\displaystyle \begin{align} \bigwedge_{\substack{h_1 \leq i \leq h_2 \\ w_1 \leq j \leq w_2}} X_{i,j} &=\bigwedge_{h_1 \leq i \leq h_2} \left( \bigwedge_{w_1 \leq j \leq w_2} X_{i,j} \right) \\ &=\bigwedge_{h_1 \leq i \leq h_2} \left( X_{i,w_1} \wedge \bigwedge_{w_1 \leq j \lt w_2} (X_{i,j+1}-X_{i,j}) \right) \\ &=\bigwedge_{h_1 \leq i \leq h_2} \left( X_{i,w_1} \wedge \bigwedge_{w_1 \leq j \lt w_2} D_j \right) \\ &=\left(\bigwedge_{h_1 \leq i \leq h_2} X_{i,w_1} \right) \wedge \left(\bigwedge_{w_1 \leq j \lt w_2} D_j \right) \\ &=\left(X_{h_1, w_1} \wedge \bigwedge_{h_1 \leq i \lt h_2} (X_{i+1,w_1}-X_{i,w_1} \right) \wedge \left(\bigwedge_{w_1 \leq j \lt w_2} D_j \right) \\ &=\left(X_{h_1, w_1} \wedge \bigwedge_{h_1 \leq i \lt h_2} C_i \right) \wedge \left(\bigwedge_{w_1 \leq j \lt w_2} D_j \right) \\ &=X_{h_1, w_1} \wedge \left( \bigwedge_{h_1 \leq i \lt h_2} C_i \right) \wedge \left(\bigwedge_{w_1 \leq j \lt w_2} D_j \right) \\ \end{align}

C_1, \dots, C_{N-1}, D_1, \dots, D_{N-1} は A,B から合計 O(N) 時間で計算できる. また, \displaystyle \bigwedge_{h_1 \leq i \lt h_2} C_i, \bigwedge_{w_1 \leq j \lt w_2} D_j については \mathbb{Z} 上では \gcd を演算, 0 を単位元とする (可換) モノイドをなすので, Segment Tree を用いて計算できる. 計算量については,

  • Segment Tree の構成に O(N (\log \max A+\log \max B)) 時間.
  • 各クエリに O(\log N+\log \max A+\log \max B) 時間.

よって, 合計 O(N (\log \max A+\log \max B)+Q(\log N+\log \max A+\log \max B)) 時間で処理できる.

なお, 今回の問題では C_1, \dots, C_{N-1}, D_1, \dots, D_{N-1} は A,B が与えられた時点で確定し, 変更しないので, Segment Tree の代わりに, Disjoint Sparse Table を用いてもよい. このとき, 計算量は

  • Disjoint Sparse Table の構成に O(\log N( N+\log \max A+\log \max B)) 時間.
  • 各クエリに O(\log \max A+\log \max B) 時間.

であり, この場合は全体で O( \log N( N+\log \max A+\log \max B)+Q(\log \max A+\log \max B)) 時間になる.

謝辞

最初, 長さ M の整数列 E における \gcd E の時間計算量を O(M \log \max E) としていたが, 31536000 さん (31536000 (@CuriousFairy315) | Twitter) の指摘と解説 により, 訂正しました. ここに感謝の意を表す. atcoder.jp