公式

F - Rectangle GCD 解説 by en_translator


Consider the case where \(h_1=w_1=1,h_2=w_2=N\). All of the following values are equal.

  • The greatest common divisor of \(A_i + B_j\) over all pairs of integers \(i,j\) such that \(1 \le i,j \le N\)
  • The greatest common divisor of \(A_i + B_1\) over all integers \(i\) such that \(1 \le i \le N\) and of \(B_j-B_{j-1}\) over all integers \(j\) such that \(2 \le j \le N\)
  • The greatest common divisor of \(A_1 + B_1\), of \(A_i - A_{i-1}\) over all integers \(i\) such that \(2 \le i \le N\), and of \(B_j-B_{j-1}\) over all integers \(j\) such that \(2 \le j \le N\)
Therefore, the general cases can also be solved by storing integer sequences \(C\) and \(D\) such that \(C_i = A_i - A_{i-1},D_j = B_j - B_{j-1}\) on segment trees that is capable of finding the greatest common divisor of elements in a given segment, so that the entire original problem can be solved in a total of \(\mathrm{O}(N+Q(\log N+\log A + \log B))\) time.

投稿日時:
最終更新: