writer 解説と同様に、本問題は次に帰着できます。

\(M\times M\)行列 \(A\) が与えられる。\(Ax = 0\pmod{X}\) となるベクトル \(x\neq 0\) が存在するかを判定し、存在するならばひとつ構築せよ。

まず、\(\det(A)\) が \(\pmod{X}\) で可逆ならば、解はありません（逆行列がとれるので）。そうでないならば、\(p\mid X\) かつ \(p\mid \det(A)\) となる素数 \(p\) がとれます。このとき \(Ax=0\pmod{p}\) となる非自明なベクトル \(x\) がとれて、それを \(X/p\) 倍すれば、解を構築できます。

したがって、\(X\) の素因数 \(p\) ごとに、次を行えばよいです。

• \(p\mid \det(A)\) となる \(p\) が見つかったら、\(Ax = 0\pmod{p}\) の解を求めることで解を構築する。
• そのような \(p\) が見つからなければ解は存在しない。

計算量は

• \(A\pmod{X}\) の計算：\(O(M^2N)\)
• \(p\) ごとの処理：\(O(M^3)\)

を合わせて \(O(M^2N+M^3\log X)\) です。