SPOJ RPAR : Raining Parabolas

6906. Raining Parabolas

Problem Summery

Given an array of n items h_i ( 0≤i<n ), we have to perform an update operation for a given range [i,j] such that, h_x = (h_x + f(x))%M, ( i≤x≤j and f(x) = ax²+bx+c ). We also have to perform a query operation for a range [i,j] such that, result = (h_i + h_i+1 + h_i+2 + … + h_j)%M.

Solution Idea

Solution idea with the help of a segment tree is quite simple. First, we need to observe the types of information we need to store on each node of the tree. As we will be facing range updates, lazy propagation can be utilized, so, we can have three carry variables, namely ca, cb, cc. If we look closely to the update procedure, parts with x² are added together and parts with x are added together and there is another part which are the constants. We can resemble them namely with variables, a, b, c, i.e. a is the variable that holds the sum for x² part, b is the variable that holds the sum for x part and c is the last one that holds the constant part. Also, we can keep the pre-computed values of sum of x² and x on tree node ranges for the ease of calculation.

Now, let’s dissect the update part. Say, on node p (i to j) we already have in a:

a₁x_i² + a₂x_i+1² + a₃x_i+2² + … + a_nx_j²

Now we want to add a new parabola (a, b, c) on this range, as only x² parts will be added here, so the new value of a on this node will be:

(a₁+a)x_i² + (a₂+a)x_i+1² + (a₃+a)x_i+2² + … + (a_n+a)x_j²

So, we can easily see the extra value added with the previous in variable a:

a * (sum of x² in range [i,j])

Similarly, for x part, i.e. variable b we can show the added value is:

b * (sum of x in range [i,j])

And for the constant part, i.e. variable c we can show the added value is:

c * n where n is the size of range [i,j];

So we can perform these updates now using lazy propagation, and query is also done in the similar way, the final result for a range is simply the sum of variable a, b, c from that range. And obviously modulus operations must be handled properly.

Have fun!

Primitive Root

Primitive root modulo n

This time, lets talk about some sort of modular arithmetic. Suppose, you are asked a peculiar question like the following:

"For a prime number p, check whether g, g², g³, ... , g^p-1 are all distinct (mod p)." [ No doubt, here, p is sufficiently large to prevent you from following naive approach ]

In other words, you are asked:

"Given any prime number p, and another positive number g, you are to tell whether g is a primitive root modulo p."

Now the question is, what is a Primitive Root?

A positive integer g is said to be a primitive root modulo n, if for every integer h such that h and n are co-prime, i.e. GCD(h,n) = 1, there is an integer k such that g^k ≡ h (mod n). This also means, g is a generator of the multiplicative group of integers modulo n.

According to the above problem, here, n is actually any prime number p, which makes the condition GCD(h,p) = 1 very obvious.

Example:

The number 3 is a primitive root in (mod 7) because

3¹=3 ≡ 3 (mod 7)
3²=9 ≡ 2 (mod 7)
3³=27 ≡ 6 (mod 7)
3⁴=81 ≡ 4 (mod 7)
3⁵=243 ≡ 5 (mod 7)
3⁶=729 ≡ 1 (mod 7)

The remainders above which are 3, 2, 6, 4, 5, and 1 are simply a permutation of 1, 2, ..., (p-1). In this case, p-1=6 because the prime number is 7.

Now, how to solve the problem easily?

As far as I know, there is no simple formula known yet to find primitive roots, however, there is a faster way to test whether a number is a primitive root rather than simply trying out all candidates. This technique can be derived from the definition of primitive roots. From its alternate definition, we know, if the multiplicative order of a number g modulo n is equal to φ(n), then g is a primitive root. In fact, the converse is also true, g is a primitive root modulo n if the multiplicative order of g is φ(n). From this axiom, we get a way to test whether, for any given g and n, g is a primitive root modulo n, as follows:

• First we compute φ(n), [ In case n is a prime p, φ(n) = p-1 ]
• Factorize φ(n), let it has k different prime factors p₁, p₂, ... , p_k, [ Even if m is as large as 2³¹, k will be around 32 ]
• Compute g^φ(n)/p_i mod n; { for i = 1, 2, 3, ... ,k }. Using a successive squaring algorithm, this can be done very easily and fast. If all the k results are different than 1, then g is a primitive root modulo n.

hu la la... , really easy. From programming approach, φ(n) can be calculated easily by standard division algorithm, dividing by the primes less than √n. [ obviously we can use Sieve of Eratosthenes to get a prime table up to √max, and if n is a prime, φ(n) = n-1 ]. Then factorize φ(n) with the same standard division algorithm and get k different primes p_i, { for i = 1, 2, 3, ... , k }. Then the rest can be done in linear time to k where each k modular exponentiation is of logarithmic complexity.

Have fun ...