Divisibility

Let $n$ and $k$ be integers. We say $k$ divides $n$, or $n$ is divisible by $k$, if $n$ is a multiple of $k$. We notate this by $k \mid n$. If $k$ does not divide $n$, then we write $k \nmid n$.

For example, $4 \nmid 20$ but $4 \nmid 21$.

How many integers are divisible by $k$ from 1 to $n$? Consider counting from $1$ up to $n$. We get a new multiple of $k$ at the end of counting each $k$ integers. The answer is $\lfloor \frac{n}{k} \rfloor$, where $\lfloor \cdot \rfloor$ is the floor operator.

The floor of $n$ (i.e. $\lfloor n \rfloor$) is formally defined as the greatest integer not exceeding $n$. So we have $\lfloor 6.6 \rfloor = 6$, $\lfloor 2 \rfloor = 2$ and $\lfloor -2.3 \rfloor = -3$. Similarly, we also have the ceiling function $\lceil n \rceil$ for the smallest integer greater than or equal to $n$. For example, $\lceil 3.3 \rceil = 4$, $\lceil 5 \rceil = 5$ and $\lceil -2.7 \rceil = -2$.

Range Queries

It is common in OI to ask for the number of integers between $L$ and $R$ satisfying some property. Usually, there is no convenient or fast way to count these integers directly.

In some cases, we have an easy way to solve the question when $L = 1$. For example, it is easy to count the number of integers divisible by $k$ from $1$ to $R$ using the formula we gave above. Let's denote the number of integers from $1$ to $n$ satisfying the required property by $A(n)$. We can use $A(n)$ to calculate the number of integers between $L$ and $R$ satisfying the required property easily: $A(R) - A(L - 1)$. In the case where we count the number of integers divisible by $k$ from $L$ to $R$, the answer is $\lfloor \frac{R}{k} \rfloor - \lfloor \frac{L - 1}{k} \rfloor$.

Note that in some problems, the answer $A(R) - A(L - 1)$ needs to be handled with caution when $L = 1$, depending on the value of $A(0)$ (which may be undefined). We will see this issue come up when we deal with prefix sums.