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 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]:
//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).