値域を \(0\) から \(V-1\) だと思って問題を解きます．

各 \(1 \leq k \leq V-1\) について，最終的に \(k \leq a\) である場合の数を数え，それらの和を取ればよいです．

\(k\) を一つ固定したとします． この時は，\(k\) 未満の値を \(0\)，\(k\) 以上の値を \(1\) に対応させ，\(01\) 列に関する問題を解けばよいです． ところで，\((a,0,0)\) の中央値は \(0\) であり，また \((a,1,1)\) の中央値は \(1\) です．つまり，\(a\) 以外の \(2\) つの値が同じになるタイミングがあれば，\(a\) の初期値(\(=A\))によらずに最終的な値が決定します． このようなケースを不活性ケースと呼び，逆にそのようなことがないケースを活性ケースと呼ぶことにします．

ここで，\(0,1\) の対称性を考えると，\(k=p\) で最終的に \(0\) になる不活性ケースの個数と，\(k=V-p\) で最終的に \(1\) になる不活性ケースの個数は等しいです． 結局，\(1 \leq k \leq V-1\) すべてについて不活性ケースだけを考えた場合，そのうちちょうど半分が \(1\) を出力することになります． よって，不活性ケースについては簡単に処理できます．

活性ケースを考えます． \(G:=gcd(N,M)\) とおきます． 活性ケースは以下のように特徴づけられます．（\(x,y\) の要素は \(0,1\) に変換されているとしています）

• 各 \(1 \leq r \leq G\) について，\(x_r=x_{r+G}=\cdots\) かつ \(y_r=y_{r+G}=\cdots\) かつ \(x_r \neq y_r\)．

これは，\(x_i,y_j\) を同時に使うことがある \(\iff i \equiv j \bmod G\) から従います．

結局，活性ケースの個数は，\((k^{N/G}(V-k)^{M/G}+k^{M/G}(V-k)^{N/G})^G\) と求まります． 活性ケースでは入力の値が操作によって変化しないため，\(k \leq A\) について上の値を足し合わせればよいです．

以上を実装すれば \(O(V(\log N + \log M))\) 時間となり，十分高速です．

解答例(c++)