ヒント → https://atcoder.jp/contests/agc063/editorial/6736

---

[1] \(\gcd(c,d)=1\) への帰着

\(g = \gcd(c,d)\) とします．まず \(k=0,1\) に対する条件から，\(x-a\) および \(x-a-b\) は \(g\) の倍数であることが必要です．したがって \(b\) が \(g\) の倍数であることが必要です（これが不成立な場合には -1 を出力します）．

また，\(x\equiv a\pmod{g}\) が必要であることも分かります．そこで \(a_0 = a\bmod g\) とおけば，\(x = a_0 + gx'\) となる整数 \(x'\) が存在します．\(a = a_0 + ga'\), \(b = gb'\), \(c=gc'\), \(d=gd'\) により整数 \(a',b',c',d'\) を定めれば，条件は \(x'\equiv a'+b'k\pmod{c'+d'k}\) となり，さらに \(x\) の非負最小性と \(x'\) の非負最小性は同値になります．

よって非負最小の \(x\) を求めるには非負最小の \(x'\) を求めればよいです．\(x',a',b',c',d'\) を改めて \(x,a,b,c,d\) とすれば結局 \(\gcd(c,d)=1\) の条件下で \(x\equiv a+bk\pmod{c+dk}\) の非負最小解を求めればよいことになります．以上により \(\gcd(c,d)=1\) の場合に帰着できました．

---

[2] \(k\) の消去

\(\gcd(c,d)=1\) の場合，任意の \(k\) に対して \(\gcd(d,c+kd)=1\) なので，

\[x\equiv a+kb\pmod{c+kd} \iff dx\equiv ad+kbd\pmod{c+kd} \iff dx\equiv ad-bc\pmod{c+kd}\]

と変形できます．そこで \(0\leq k\leq N-1\) に対する \(c+kd\) 全体の最小公倍数を \(L\) とし，\(u = ad - bc\) とおけば，条件は \(dx \equiv u\pmod{L}\) と表すことができます．\(\gcd(d,L)=1\) なので，この合同式は \(L\) を法として一意な解を持つことが分かります（特に解は存在します）．しかし \(L\) は一般には巨大なので，解の計算方法は自明ではありません．

---

[3] 答の計算

\(L\) は一般には巨大ですが，区間篩の要領でその素因数分解は高速に計算できます．詳細は [4] を参照してください．特に，\(L\bmod d\) や \(L\bmod 998244353\) は高速に計算できることに注意してください．

\(dx\equiv u\pmod{L}\) と，\(dx - u = Ly\) となる整数 \(y\) が存在することは同値です．そこでまず \(Ly\equiv -u\pmod{d}\) となるような最小の非負整数 \(y=y_0\) を求めます．\(y_0\) は \(L\bmod d\) の値から計算できます．

すると，\(Ly\equiv -u\pmod{d}\) の解は，\(y=y_0+td\) （\(t\) は整数）として表すことができます．\(x\) は

\[x = \frac{u+L(y_0+td)}{d}\]

と表すことができます．これが非負になるような最小の \(t\) を求めましょう．

\(L \leq |u|\) のときは，\(L\) の値を求めることによって解けます．以下 \(L>|u|\) とします．このときには，

• \(u<0\) かつ \(y_0 = 0\) ならば \(t=1\)
• そうでないならば \(t=0\)

となることが容易に分かります．

\(t\) が分かれば，あとは \(L\bmod 998244353\) の値を利用すれば \(x\bmod 998244353\) を計算できます．以上により答が計算できました．

---

[4] \(L\) の素因数分解の計算

\(L\) を素因数分解するために，各 \(A_k = c + dk\) をすべて素因数分解します．これは次の方法により行えます．

(1) 定数 \(X\) を \(X^2\geq \max A\) となるようにとる．\(X\) 以下の素数全体の集合 \(P\) を求めておく．

(2) 各 \(p\in P\) に対して次を行う．

• \(p | c + dk\) となるような最小の非負整数 \(k\) を求める．
• \(i = k, k+p, k+2p, \ldots\) に対して \(A_i\) が \(p\) で割り切れる限り \(p\) で割る

(3) 最終的に \(A_i > 1\) であるような \(A_i\) はすべて素数である．

なお，\(X > N\) ととっておくことで，(3) で残す素数が相異なるようにもできます．

計算量について述べます．(1) は例えば Eratosthenes の篩により \(O(X\log\log X)\) 時間で行えます．(2) は \(k\) の計算に \(O(\log p)\) 時間，\(p\) で割れるものの除算に \(O(N/p+\log X)\) 時間などと評価できます．\(X\) 以下の \(p\) の個数が \(O(X/\log X)\) 個であることや，それらの逆数の和が \(O(\log\log X)\) であることを用いると，これらの計算は全体で \(O((N+X)\log\log X)\) 時間であることが分かります．