AT_agc063_d.[AGC063D] Many CRT

给定正整数 $N,\ a,\ b,\ c,\ d$。

请判断是否存在非负整数 $x$，使得对于所有 $k=0,1,\ldots,N-1$，都有 $x\equiv a+kb\pmod{c+kd}$。如果存在，请输出所有满足条件的 $x$ 中最小的一个对 $998244353$ 取模的结果；如果不存在，请输出 $-1$。

输入为一行，包含五个整数：

$N\ a\ b\ c\ d$

如果不存在满足条件的非负整数 $x$，请输出 $-1$。如果存在，请输出所有满足条件的 $x$ 中最小的一个对 $998244353$ 取模的结果。

限制

• $2\leq N\leq 10^6$
• $1\leq a,b,c,d\leq 10^6$

样例解释 1

满足 $x\equiv 1\pmod{3}$ 且 $x\equiv 3\pmod{7}$ 的最小非负整数为 $x=10$。

样例解释 2

不存在满足 $x\equiv 1\pmod{10}$ 且 $x\equiv 2\pmod{20}$ 的非负整数。

样例解释 3

满足条件的最小非负整数为 $x=0$。

样例解释 4

满足条件的最小非负整数为 $x=15977769171609124$。

由 ChatGPT 4.1 翻译