分数: 1200 点
问题陈述
给你正整数 N, a, b, c, d.
判断是否存在非负整数 x 这样 x\equiv a+kb \pmod{c+kd} 对于每个 k=0,1,\ldots,N-1。如果存在,找到最小的这样的 x 模数 998244353.
约束
- 2\leq N\leq 10^6
- 1\leq a,b,c,d\leq 10^6
输入
输入由标准输入按以下格式给出:
N a b c d
输出
如果没有非负整数 x 满足条件,打印 -1。
否则,打印最小的这样的 x 模数 998244353.
示例输入 1
2 1 2 3 4
示例输出 1
10
x=10 是最小的非负整数,使得 x\equiv 1\pmod{3} 和 x\equiv 3\pmod{7}.
示例输入 2
2 1 1 10 10
示例输出 2
-1
没有非负整数 x 满足 x\equiv 1\pmod{10} 和 x\equiv 2\pmod{20}.
示例输入 3
100 20 30 2 3
示例输出 3
0
x= 0 是满足条件的最小非负整数。
示例输入 4
9 12 34 56 78
示例输出 4
827501367
x=15977769171609124 是满足条件的最小非负整数。