← 返回题目列表

AtCoder · agc063_d

D. 许多CRT

中文机器翻译题面 查看原题

分数: 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 是满足条件的最小非负整数。