# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Jeevan Jyot Singh

*Hriday*

**Tester:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

1123

# PREREQUISITES:

Basic math

# PROBLEM:

Given a stick of length L, you want to break it into exactly K positive integer-sized parts A_1, A_2, \ldots, A_K

What is the minimum possible value of \sum_{i=1}^{K-1} |A_i - A_{i+1}|?

# EXPLANATION:

The answer is 0 if K divides L and 1 otherwise.

## Proof

If K divides L, obviously we can make K parts of size \frac{L}{K} and the given expression evaluates to zero.

Otherwise, it’s always possible to obtain a difference of 1. Here’s a construction:

Let x = \left\lfloor \frac{L}{K}\right\rfloor and y = \left\lceil \frac{L}{K}\right\rceil.

Also, let r denote the remainder when L is divided by K. Since K doesn’t divide L, 0 \lt r \lt K.

Now, set A_1 = A_2 = \ldots = A_r = y, and everything else equal to x.

It’s easy to see that the sum of all A_i is L. Further, almost every pair of adjacent terms are equal: only A_r and A_{r+1} are not equal, and they differ by |x-y| = 1, as required.

# TIME COMPLEXITY

\mathcal{O}(1) per test case.

# CODE:

## Editorialist's code (Python)

```
for _ in range(int(input())):
n, k = map(int, input().split())
print(1 if n%k > 0 else 0)
```