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$ 取模的结果。

样例 1

输入

2 1 2 3 4

输出

10

样例 2

输入

2 1 1 10 10

输出

-1

样例 3

输入

100 20 30 2 3

输出

0

样例 4

输入

9 12 34 56 78

输出

827501367

说明/提示

限制

• $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 翻译