AtCoder Grand Contest 063
翻译中…
Problem Statement
翻译中…
You are given positive integers $N, a, b, c, d$.
翻译中…
Determine whether there is a non-negative integer $x$ such that $x\equiv a+kb \pmod{c+kd}$ for every $k=0,1,\ldots,N-1$. If it exists, find the smallest such $x$ modulo $998244353$.
翻译中…
Constraints
翻译中…
$2\leq N\leq 10^6$$1\leq a,b,c,d\leq 10^6$
翻译中…
Input
翻译中…
The input is given from Standard Input in the following format:
翻译中…
N a b c d翻译中…
Output
翻译中…
If there is no non-negative integer $x$ satisfying the condition, print -1. Otherwise, print the smallest such $x$ modulo $998244353$.
翻译中…
样例
Input #1
2 1 2 3 4
Output #1
10
$x=10$ is the smallest non-negative integer such that $x\equiv 1\pmod{3}$ and $x\equiv 3\pmod{7}$.
Input #2
2 1 1 10 10
Output #2
-1
No non-negative integer $x$ satisfies $x\equiv 1\pmod{10}$ and $x\equiv 2\pmod{20}$.
Input #3
100 20 30 2 3
Output #3
0
$x= 0$ is the smallest non-negative integer satisfying the condition.
Input #4
9 12 34 56 78
Output #4
827501367
$x=15977769171609124$ is the smallest non-negative integer satisfying the condition.
题目信息
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（CI 管线），如有出入请以原文为准。