まず、 \(h(x):=f(x)-g(x)\) として \(h(x)\) と \(0\) を比較する問題と読み替えます。

\(K=-1,0,1\) の場合は簡単です。また、 \(K\) が負の時は奇数次の項を適当に処理して \(0<K\) とします。

\(h(K)\) をすべての桁の値が非負であるように \(K\) 進法に変換できるならば \(0 \le h(K)\) です。可能ならば桁数は \(\max(N,M)+30\) 程度で抑えられますから、愚直に下の桁から \(0\) 以上になるように調整していくことでこの問題を解くことができます。

時間計算量は \(1\) ケース当たり \(O(\max(N,M))\) です。

想定解 (C++)