Hints→ https://atcoder.jp/contests/agc063/editorial/6881

---

[1] Reduction to \(\gcd(c,d)=1\)

Let \(g = \gcd(c,d)\). First, the condition for \(k=0,1\) requires that \(x-a\) and \(x-a-b\) must be multiples of \(g\). Thus, \(b\) must be a multiple of \(g\) (print -1 if this is not the case).

We also see that \(x\equiv a\pmod{g}\) is necessary. Then, if we let \(a_0 = a\bmod g\), there is an integer \(x'\) such that \(x = a_0 + gx'\). If we define integers \(a'\), \(b'\), \(c'\), and \(d'\) by \(a = a_0 + ga'\), \(b = gb'\), \(c=gc'\), and \(d=gd'\), then the condition becomes \(x'\equiv a'+b'k\pmod{c'+d'k}\), and \(x\) is the smallest non-negative if and only if \(x'\) is the smallest non-negative.

Thus, to find the smallest non-negative \(x\), we should find the smallest non-negative \(x'\). If we redefine \(x,a,b,c,d\) as \(x',a',b',c',d'\), we should find the smallest non-negative solution to \(x\equiv a+bk\pmod{c+dk}\) under the condition \(\gcd(c,d)=1\). This completes the reduction to \(\gcd(c,d)=1\).

---

[2] Elimination of \(k\)

If \(\gcd(c,d)=1\), then \(\gcd(d,c+kd)=1\) for any \(k\), so we can do the following transformation:

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

Then, if we let \(L\) be the least common multiple of all \(c+kd\) for \(0\leq k\leq N-1\) and let \(u = ad - bc\), the condition can be expressed as \(dx \equiv u\pmod{L}\). Since \(\gcd(d,L)=1\), we see that this congruence has a unique solution modulo \(L\) (in particular, the solution exists). However, \(L\) is generally huge, so it is not trivial to compute the solution.

---

[3] Computing the answer

Although \(L\) is generally huge, its prime factorization can be computed quickly in the manner of an interval sieve. See [4] for details. Note in particular that \(L\bmod d\) and \(L\bmod 998244353\) can be computed quickly.

\(dx\equiv u\pmod{L}\) is equivalent to the existence of an integer \(y\) such that \(dx - u = Ly\). We first find the smallest nonnegative integer \(y=y_0\) such that \(Ly\equiv -u\pmod{d}\). \(y_0\) can be calculated using the value \(L\bmod d\).

Then, the solution of \(Ly\equiv -u\pmod{d}\) can be expressed as \(y=y_0+td\), where \(t\) is an integer. \(x\) can be expressed as:

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

Let us find the smallest \(t\) that makes it non-negative.

If \(L \leq |u|\), we can solve it by finding the value of \(L\). Now, let \(L>|u|\). Then, we can easily see the following:

• if \(u<0\) and \(y_0= 0\), then \(t=1\);
• otherwise, \(t=0\).

Once \(t\) is known, \(x\bmod 998244353\) can be computed by using the value \(L\bmod 998244353\). We now have the answer.

---

[4] Computing prime factorization of \(L\).

To prime factorize \(L\), let us prime factorize every \(A_k = c + dk\). This can be done as follows.

(1) Take a constant \(X\) such that \(X^2\geq \max A\). Find the set \(P\) of all primes at most \(X\).

(2) For each \(p\in P\), do the following.

• Find the smallest non-negative integer \(k\) such that \(p | c + dk\).
• For \(i = k, k+p, k+2p, \ldots\), keep dividing \(A_i\) by \(p\) as long as it is divisible by \(p\).

(3) In the end, every \(A_i\) such that \(A_i > 1\) is prime.

One can take \(X > N\) so that the primes left in (3) are distinct.

Let us discuss the computational complexity. (1) can be done in \(O(X\log\log X)\) time, for example, by the sieve of Eratosthenes. (2) can be evaluated as \(O(\log p)\) time to compute \(k\), \(O(N/p+\log X)\) time to divide what is divisible by \(p\), and so on. Using the fact that the number of \(p\) under \(X\) is \(O(X/\log X)\) and the sum of their inverses is \(O(\log\log X)\), we see that these calculations take \(O((N+X)\log\log X)\) time in total.