### PROBLEM LINK:

**Author:** Anudeep Nekkanti

**Tester:** Minako Kojima

**Editorialist:** Lalit Kundu

### DIFFICULTY:

MEDIUM-HARD

### PRE-REQUISITES:

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:

Read post in pre-requisite if you don’t know about Mo’s algorithm.

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

**10**.

^{6}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]:
//update the answer
//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)**.