公式解説で \(O(N(\log A+ \log B)+Q(\log N + \log A + \log B))\) となっている理由について解説します。

結論から言うと、長さ \(L\) で最大値が \(M\) の数列 \(A\) に対して最大公約数を求める計算量は、 \(O(L + \log M)\) です。

最大公約数を次のように求めることを考えます。

def gcd(a, b):
  return b if a == 0 else gcd(b % a, a) # 連続的にgcdを求める際はa<bのことが多いのでこの順

この関数に対して、次のように最大公約数を計算してみましょう。

G = 0 # 上のgcdでは0が単位元となる
for i in A: G = gcd(G, i)

この関数の挙動について考えていきます。

今 \(i\) 番目まで計算し、 \(G=\gcd(A_1, \ldots, A_i)\) となっているとします。 次に \(i+1\) 番目との最大公約数を計算することを考えます。

まず、 \(G \leq A_{i+1}\) のとき、 \(1\) 回目の計算で \(A_{i+1} \leftarrow A_{i+1} \mod G\) となります。従って、 \(G > A_{i+1}\) と考えても差し支えありません。

\(A_{i+1} \neq 0\) であるとします。 すると、次の計算で \(G\) を \(A_{i+1}\) で割った余りに置き換えることになります。

\(A_{i+1}\) が \(G\) の半分以上のとき、 \(G\) を \(A_{i+1}\) で割った余りは \(G\) の半分未満です。逆に、 \(A_{i+1}\) が \(G\) の半分未満のとき、 \(G\) を \(A_{i+1}\) で割った余りはもちろん \(G\) の半分未満です。よって、 \(\gcd\) 関数が再帰的に \(2\) 回呼ばれる度に少なくとも答えが半分以下になることが分かります。

\(M\) を高々 \(\log M\) 回だけ半分以下にすると \(1\) になること、片方が \(1\) ならば高々 \(2\) 回の演算で求まることから、計算量 \(O(L + \log M)\) が導けます。

余談

\(i\) 番目のフィボナッチ数を \(F_i\) としたとき、 \(\gcd(F_n, F_{n-1})\) は \(\Theta(n)\) 回の計算を必要とします。これは、 \(F_n\) を \(F_{n-1}\) で割った余りが \(F_{n-2}\) であることから、順にフィボナッチ数列の値が出てくることから分かります。

また、 \(n\) 番目のフィボナッチ数は \(\frac{1}{\sqrt 5}((\frac{1+\sqrt 5}{2})^n - (\frac{1-\sqrt 5}{2})^n)\) であることから、 \(M= O(\log n)\) となることが分かります。従って、これが最悪計算量を達成します。

これ以外に最悪計算量を達成するペアが無いのか？という問題に関しては、AGC015-F Kenus the Ancient Greek などを参考にしてください。

また、今回の問題で用いた計算量解析はあくまで連続的に最大公約数を求める場合にのみ適用されます。従って、例えばセグメント木上の二分探索などで連続性が失われる計算をすると、従来通り \(\log\) が付くことに注意してください。yukicoder contest 245-D Make One With GCD 2 などが二分探索だと遅くなる問題として有名です。

余談2

def gcd(a, b):
  return a if b == 0 else gcd(b, a % b)

と書かれることがありますが、連続的に計算する場合はこれだとちょっと遅いです。

def gcd(a, b):
  return b if a == 0 else gcd(b % a, a)

と比較した場合、ランダムな十分な長さの数列に対して2～3倍ほどの差がでました。

また、後者の関数は \(a\) が殆ど変化しないことが期待できます。そこで、Barrett Reductionを行ったところ少し速くなりました。一方、gcdをbinary gcdで実装したところかなり遅くなりました。

これらの実験結果から、最大公約数を求める際には解説の最初に記載した関数が良いと考えられます。再帰より非再帰の方が速いので、下記の関数でも構いません。

def gcd(a, b):
  while a != 0:
    b %= a
    if b == 0: return a
    a %= b
  return b

余談3

区間の最大公約数は、Segment Tree以外の方法で解くこともできます。 最大公約数を求める関数 \(\gcd\) は次の性質を持っています。

• \(0\) 以上 \(M\) 以下の整数に対して閉じている \((0 \leq \gcd(a, b) \leq M)\)
• 単位元 \(0\) を持つ \((\gcd(0, a) = \gcd(a, 0) = a)\)
  余談ですが、単位元が無い場合は適当な値(nullなど)を単位元に仕立て上げることもできます。
• 結合法則を満たす \((\gcd(\gcd(a, b), c) = \gcd(a, \gcd(b, c)))\)
• 交換法則を満たす \((\gcd(a, b) = \gcd(b, a))\)
• 吸収元 \(1\) を持つ \((\gcd(1, a) = \gcd(a, 1) = 1)\)
• 冪等である \((\gcd(a, a) = a)\)

すなわち、 \(\gcd\) は結び半束です。結び半束は可換モノイドとしての性質も持つことに注意してください。

さて、区間に対して演算を行うデータ構造は幾つかあります。代表的なものを列挙してみましょう。

• 累積和
  演算が群を成すときに適用できます。あるいは、先頭からのクエリのみならモノイドで十分です。
  今回の場合は、 \(\gcd\) に逆元が存在しないことから適用できません。
• Segment Tree
  演算がモノイドを成すときに適用できます。 \(\gcd\) はモノイドなので適用できます。 計算量は \(O(N \log M)/O(\log N + \log M)\)です。
• Sparse Table
  演算が冪等モノイドを成すときに適用できます。 \(\gcd\) は冪等モノイドなので適用できます。 計算量は \(O(N(\log N + \log M))/O(\log M)\)です。
• Disjoint Sparse Table
  演算がモノイドを成すときに適用できます。\(\gcd\) はモノイドなので適用できます。 計算量は \(O(N(\log N + \log M))/O(\log M)\)です。
  なお、Disjoint Sparse Tableは計算量と汎用性という観点では上位互換ですが、実際はやや定数倍がSparse Tableより重い点に注意してください。
  また、再帰的にDisjoint Sparse Tableを組み合わせることで計算量を\(O(N(\alpha(N) + \log M))/O(\alpha(N) + \log M)\) にすることができますが、あまり実用的ではありません。
• Sliding Window Aggregation
  演算がモノイドを成し、クエリで与えられる区間が単調性を満たすときに適用できます。 今回は、クエリが単調でないため適用できません。