No.1048 Zero (Advanced)
stoq
tran0826Problem Statement
T-kun has an integer $N$. Initially, $N=0$.
T-kun performs the following operation $K$ times.
- Choose one integer $i \ (L \leq i \leq R)$. Then, replace $N$ with the remainder when $N+i$ is divided by $M$.
Does there exist a sequence of operations such that $N=0$ holds again after the $K$ operations?
If one exists, print Yes; otherwise, print No.
Input
$L\ R\ M\ K$
$L,R,M,K$ are integers.
$0 \leq L \leq R \leq 10^9$
$1 \leq M \leq 10^9$
$0 \leq K \leq 10^9$
Output
If a sequence of operations satisfying the condition exists, print Yes; otherwise, print No. Print a newline at the end.
Sample
Sample 1
Input
3 7 5 2
Output
Yes
For example, if you choose $i = 3$ in the first operation and $i = 7$ in the second operation, $N$ changes as $0 \to 3 \to 0$.
Sample 2
Input
2 3 4 1
Output
No
No matter how you choose $i$, you never get $N=0$.
Sample 3
Input
2 3 4 0
Output
Yes
No operation is performed, so $N=0$ remains as it is.
Sample 4
Input
10 53 100 2
Output
Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。