Ideal Farm
Contest: Codeforces Round 747 (Div. 2)
Difficulty rating: 2400
Tags: constructive algorithms, math

Theofanis decided to visit his uncle's farm. There are $$$s$$$ animals and $$$n$$$ animal pens on the farm. For utility purpose, animal pens are constructed in one row.

Uncle told Theofanis that a farm is lucky if you can distribute all animals in all pens in such a way that there are no empty pens and there is at least one continuous segment of pens that has exactly $$$k$$$ animals in total.

Moreover, a farm is ideal if it's lucky for any distribution without empty pens.

Neither Theofanis nor his uncle knows if their farm is ideal or not. Can you help them to figure it out?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first and only line of each test case contains three integers $$$s$$$, $$$n$$$, and $$$k$$$ ($$$1 \le s, n, k \le 10^{18}$$$; $$$n \le s$$$).

Output format:
For each test case, print YES (case-insensitive), if the farm is ideal, or NO (case-insensitive) otherwise.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
For the first and the second test case, the only possible combination is $$$[1]$$$ so there always will be a subsegment with $$$1$$$ animal but not with $$$2$$$ animals.

Example input:
4
1 1 1
1 1 2
100 50 200
56220 47258 14497

Example output:
YES
NO
NO
YES

Editorial:
The problem is the same as:
We have an array $$$a$$$ of length $$$n$$$ where every element of it is a positive integer and the sum of the whole array is $$$s$$$. If no matter how we construct the array $$$a$$$, we can find a non-zero length subarray which has sum equal to $$$k$$$ print "YES" else print "NO".
If $$$s = k$$$ then the answer is obviously "YES" and if $$$s < k$$$ then the answer is obviously "NO".
Let $$$pre[i] = \sum_{j=1}^{j<=i} a[j]$$$ ($$$1$$$ - indexed)
All the elements of array pre are different as all $$$a[i]$$$ are positive integers. Let $$$b[i] = pre[i] + k$$$ but we also have $$$b[0] = k$$$.
Again all the elements of $$$b$$$ are different because all $$$a[i]$$$ are positive integers.
Array $$$pre$$$ has size $$$n$$$ and array $$$b$$$ has size $$$n + 1$$$.
If and only if an element from $$$pre$$$ is equal to an element from $$$b$$$ then it means that $$$pre[i] = pre[j] + k$$$ or $$$pre[i] = k$$$. If it is the second case then obviously there is a subarray with sum equal to $$$k$$$.
If it's the first case then $$$pre[i] - pre[j] = k$$$ so the subarray $$$[j+1, i] $$$ has sum $$$k$$$.
But when do we have an equation in these two arrays?
There are $$$n + (n + 1) = 2n + 1$$$ elements and they can be values from $$$1$$$ to $$$s+k$$$.
If the maximum number of distinct elements that we can take is less than $$$2n + 1$$$ the answer is "YES" else the answer is "NO".
Let $$$m$$$ be the maximum number of elements that we can take.
We go through the last k elements ($$$[s-k+1,s]$$$) and we count the number of elements that have the same modulo $$$k$$$.
For each element in this range, if there are odd elements that have the same modulo, we can't take all of them because for every element $$$x$$$ that we add in $$$pre$$$ that we also add $$$x+k$$$ to $$$b$$$. Thus one element would have a $$$x+k$$$ out of range.
Therefore we count all the elements that have odd elements with the same modulo $$$k$$$ and subtract them from $$$s+k$$$ to find $$$m$$$.