• \((M^P)_{i,j}=M_{i,j} \times X_{i-j+1}\)
• \(X\) が等比数列

という条件から頑張って式変形すると、

\(M_{i,j}=\frac{a\times \prod_{k=i}^{j-1}t_k}{(j-i)!}\)

となる \({t_1,t_2,\dots,t_{N-1}}\) が存在することが必要十分条件となります。

\(i \geq j\) の時に \(M_{i,j}\) が正整数になる条件を考えます。任意の素因数 \(p\) について \(\prod_{k=1}^{i-1}t_k\) を素因数分解したときに \(p\) で割り切れる回数を \(e_i\)(\(i=1,2,\dots ,N\)) とすると、 \(M_{i,j}\) が正整数になる条件は \(e\) の2変数の差の不等式として表されます。 また、\(GCD\) の条件も2変数の差の不等式で表されます。これらは双対を取ることで最短路問題に置き換えられます（いわゆる牛ゲーです）。

小課題

\(p\) として考えるべき素数は、 \(A_k,B_k,C_k,D_k\) の素因数のみで十分です。各 \(p\) についてグラフを構築し、各クエリに対して最短路問題を解けば十分間に合います。グラフには負辺が含まれることに注意してください。

満点

\(M[i][j]\) が正整数になる条件より貼られる辺を普通辺、\(GCD\) の条件より貼られる辺を例外辺と呼ぶことにします。普通辺のみを使うときの \(2\) 頂点間の距離は、ルジャンドルの公式の結果を前計算しておけば \(O(1)\) で求められます。例外辺の本数を \(S\) として、素因数ごとのグラフについて解く解法を \(2\) 通り考えます。

\(O(S^3+QS^2)\) 解法

例外辺の端点のみを用いたグラフを用意し、すべての \(2\) 頂点間に基本辺のみを用いた場合の最短路の長さの辺を貼って、ワーシャルフロイド法により各 \(2\) 頂点間の距離を求めます。各クエリ(\(E_q,F_q\))に対して、 \(E_q\) から基本辺のみを用いる場合と例外辺を用いる場合で場合分けをすると、前者は \(O(1)\) 、後者は \(O(S^2)\) なので、全体で \(O(S^3+QS^2)\) で解くことができます。

\(O((S+N \log {p}{N})(N+QlogN))\) 解法

\(N\) 頂点のグラフに例外辺をすべて貼ります。 \(a\) を \(p\) が割り切る回数を \(c\) とすると、頂点 \(j\) から頂点 \(j\) に基本辺のみを用いて移動するときの距離は \(c-Legendre(j-i)\) になります。 \(c=0\) なら、 \(j-i\) が \(p\) のべき乗になるような \(2\) 頂点間 \(i,j\) にのみ辺を貼れば十分です。 \(c\neq 0\) の場合は、各頂点を \(2\) つずつに分けたグラフを用意し、適切に辺を貼れば、辺が \(O(S+N \log {p}{N})\) 本のグラフで表現できます。ベルマンフォード法で、ある \(1\) 頂点からの最短路を求め、それをポテンシャルとして各クエリに対してダイクストラ法により最短路を求めます。計算量は \(O((S+N \log {p}{N})(N+QlogN))\) です。

まとめ

これらの解法を使い分けることで、実行時間に間に合わせて解くことができます。