# ANUAAA - Editorial

Author: Anudeep Nekkanti
Tester: Minako Kojima
Editorialist: Lalit Kundu

MEDIUM-HARD

Mo’s algorithm
Number Theory

### PROBLEM:

For a prime P and array A, F(A, L, R, P) denotes number of A[i], (L ≤ i ≤ R) divisible by P. Given an array A of size N and another array B of size M, find where,
L = (B[i] + B[j]) % N
R = (B[i] - B[j] + N) % N

### EXPLANATION:

If we note that L and R being generated here are random. So, we’ll have to calculate F(A, L, R, P), for each query. So our problem now is that:
Given M * M queries of form L, R, for each query find Sum[F(A, L, R, P)2] for all primes p less than 106.

Now, we can note here that if we have answer for query (L, R), how fast can we calculate answer for (L, R+1). Suppose we have an array cnt, where cnt[i] denotes the F(A, L, R, i) (i are primes). So our answer here is sum{cnt[i]2} for all i primes.
Now, we have to make certain changes in cnt array since a new number A[R+1] has been added.

``````ans = answer for (L,R)
for all p = prime factors of A[R+1]:
//answer is affected due to change in cnt[p]
ans -= cnt[p]*cnt[p]
cnt[p]++;
ans += cnt[p]*cnt[p]
print ans
``````

And, similarily we can also remove a number from our answer.
In complexity: O(number of prime factors), we can insert/delete a number from our data structure.
So, basically, what we have here is a data structure in which we can insert/delete a number in O(K), where K < number of distinct prime factors of number(worst case 7).
If we have all the numbers in range [L, R] organized in our data strcture, we can transform to [L’, R’] in O((|L-L’| + |R-R’|) * K).

Now, what we’ll use here is popularly known as Mo’s algorithm among chinese. It’s a offline query algorithm. We process all our queries in such a order such that transform cost is minmised.
Here’s the sorting function we use:

``````//we break array A into sqrt(N) chunks.
S = the max integer number which is less than sqrt(N);
bool cmp(Query A, Query B)
{
//if starting point belongs to different chunks
//sort on increasing starting point
if (A.l / S ！= B.l / S) return A.l / S < B.l / S;

//if starting point is present in same chunk
//sort according to decreasing ending point.
return A.r > B.r
}
``````

We sort all the queries by this comparator, and process all queries in order. It can be proved easily that the total transform cost is O(N * sqrt(N) * K).

### SOLUTIONS:

A solution that doesn’t uses the sqrt(N) decomposition:

We can first sort the array b and then just process the queries in original order, that is:

``````for (int i = 0; i < m; i++)
for (int j = 0; j < m; j++)
process query L = b[i] + b[j], R = b[i] - b[j]
``````

We can process queries just the same way it is described in editorial, that is doing O((∆L + ∆R) · K) stuff to move between adjacent queries.

One can prove that due to sorted order of b the total complexity will be O(N · M · K), but with pretty big constant factor.

2 Likes