# Problem Link:

**author**: Tasnim Imran Sunny

**tester**: Roman Rubanenko

**editorialist**: Utkarsh Lath

# Difficulty:

Medium

# Pre-requisites:

offline processing of queries, factorizing small integers

# Problem:

Given a sequence of **N** integers **a[i]**, answer **Q** queries. Each query is described by three integers **L**, **R**, **K** meaning *how many numbers in the sub-array from L to R are multiple of K*.

# Quick Explanation:

The queries can be answered *online*(meaning answering all queries, one by one, as soon as they are asked) as well as *offline*(meaning taking all the queries, processing them together and return their results), the offline solution goes as follows(online solution is also discussed later):

Each (**L**, **R**, **K**) query can be broken into two queries, query(**L-1**, **K**) and query(**R**, **K**). (query(**L**, **R**, **K**) = query(**R**, **K**) - query(**L-1**, **K**)).

The array **a** is processed from left to right and **count[k] = number of multiples of k seen so far** is maintained. Query (**x**, **K**) is answered immediately after **a[x]** is processed.

# Explanation:

## via offline processing

Given a single integer **a[i]**, it would be easy to tell which **k**ās are divisible by **a[i]**(by factorizing **a[i]**'s). Therefore, it would also be easy to answer the queries for a fixed array, because we could factorize each number and store the number of occurrences of each factor.

Therefore, the real hardness of problem lies in the fact that we are being queried arbitrary subarrays.

If a problem can be solved efficiently for an array, and more elements can be also be added to the array efficiently, without hurting the ability to solve the problem efficiently, then the problem can also be solved (offline) for arbitrary prefixes(or suffixes) of the array.

Our understanding of the problem so far satisfies the above property, so we can answer queries efficiently for any prefix of the array(I will answer the how part in a short while).

This means, we can answer queries which ask *āhow many numbers among the first L are multiples of Kā*

But, solving the above problem would be sufficient for us as well, because we can always break a query (**L**, **R**, **K**) into two queries (**R**, **K**) and (**L-1**, **K**), which asks for number of multiples of **K** among the first **R** and first **L-1** numbers respectively.

**Note** that this technique works only because ā+ā operation is *invertible*. Therefore, if the problem asked for āhighest multiple of K in the interval L to Rā, we could not use this method. The online method described in next section will be upto the task.

### Offline processing

To accomplish solving the problem for arbitrary prefixes, given it can be solved for the array, can be done as follows:

```
sort all queries (x, K) in increasing order of x.
make an array named count of size K_max, and initialize all entries to 0
for i = 1 to N
for each j | a[i]
count[j++]
for all queries of the form (i, K):
report answer of query = count[K]
```

For further details on how to implement this, look at testersā or editorialistsā code.

The overall time complexity will be **O(A_max ^{0.5} * N + Q log Q)** if all factors are found by trial division.

This can be speeded up to **O(A_max * log A_max + N * F + Q log Q)**, where **F** is the maximum number of factors any integer can have. This speed-up can be achieved by precomputing all factors of all numbers upto **A_max**.

```
for i = 1 to A_max
for j = i; j < A_max; j+=i
factors[j].push_back(i)
```

Both the solutions were acceptable. These two(with and without pre-computing factors) solutions were used by the Tester and the Editorialist respectively.

## Online Algorithm

The main idea is that each number in the array can be multiple of at most 128 numbers(refer list of highly composite numbers). Therefore, for each value of K, we can store locations of all of its multiples, and answer queries by binary searching.

```
for i = 1 to N
input a[i]
for j in factors of a[i]
occurances[j].push_ back(i)
for i = 1 to Q
input L, R, K
x = smallest index i such that occurances[K][i] >= L
y = smallest index i such that occurances[K][i] > R
// x and y can be found by binary search, or STL's [lower_ bound](http://www.cplusplus.com/reference/algorithm/lower_bound/) and [upper_bound](http://www.cplusplus.com/reference/algorithm/upper_bound/) functions
report y - x
```

The problem setter used an offline variant of the above solution.

# Related problems

For practice on offline processing of queries(need not be āeasyā), refer to

1

2

3

4

# Solutions:

Setterās solution

Testerās Solution

Editorialistās Solution