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_max0.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