First things first, let be the primitive root of (Primitive roots can be calculated in ). So by definition, we can express any number using some power of under modulo . Let, . Notice that, for the given mod, , there is no such value s.t. . So we don't have to worry about dealing with zeroes. All for can be calculated in .
So our equation becomes
So we have to compute the sum of the products .
Let . We will compute for each from to .
Build an array where is the maximum index such that for each index , MEX of the subarray is .
Now, let's build the array for each from to in order. To generate the array for , update the array using the occurrences of in . For that we have to perform:
range updates like set for some range and some integer .
range queries like sum of .
We can solve this part using Segment Tree Beats. Please see the setter’s solution for more clarity.
One can also observe that is a non-decreasing array. So the operations can also be done using a normal segment tree.
Overall Complexity: .
Setters solution: smash here .