How this problem should be approached…??
5 Likes
Can anyone help me with this problem …??
but your help is also welcomed 
I may not clear in this explanation because I myself was unable to solve this beautiful problem .
I thought of making a 20 x 20 matrix in which each cell (i,j) can be used to represent number of ways to use a group of j integers between 1 to 20 and i is the gcd of the group.
Then rest of it was pure combinatorics.
By the way, how much was your score?
I was not able to solve this problem and in Even Paths question i used DFS to find all paths and counted the nodes but it also gave me partial points only so overall it was a disaster for me 
Matrix Exponentiation is the answer
1 Like
It would be nice if you could explain little bit 
get a O(n) dp solution and then apply Matrix Exponentiation to reduce it to Log(n).
Check this out :
[Tutorial]A Complete Guide on Matrix Exponentiation - Codeforces
O(n) is a standard Dp solution as to check it ends at which number
I thought about it the same. But the constraints for number of nodes was 10^5. I thought about adding edges to a tree because it would have been easier for a tree and then adding the remaining edges. But couldn’t make it.
@c_007 Thanks for helping, i am in learning phase and it would be of great help if you could help little bit with implementation part 
for basics check out Fibonacci in log(n) then
AsMApR - Online Java Compiler & Debugging Tool - Ideone.com with help of this solve the question on your own.
Thanks 
As the value of the elements can be upto 20 only, so if the length of the segment [L, R] is greater than 20 then it means that the elements are repeated.
So, at first find the number of possible combination such that the GCD is ‘x’. This can be done by iterating over every possible bitmask 2^20.
Now, as no two query range intersect. So, we can process the query independently.
For each query we have the GCD and we have the bitmasks which will satisfy that GCD (maximum bitmasks for a gcd is 2^20). Now for each bitmask we will find the number of ways to fill subarray of size (R - L + 1). Suppose the number of active bits in current bitmask is T. So, the number of ways to fill (R - L + 1) (let this be s) sized subarray is just the co-efficient of x^s in the expansion of (x + x^2 + x^3 + .... )^T . We can simplify this using the sum upto infinity formula and then find the combinatoric formula of the form (nCr) for this and as the value of T can be atmost 20, we can iterate over the values and find the value of nCr.
Now we have the possible set of values for the given ranges. Now, count the number of unmentioned indexes (let this be Y) and multiply 2^Y to the final answer.
sorry for my poor english. You can ask if something is unclear OR if you seem this process doesn’t work ;P.
1 Like
Which one Even Paths or Candy Love…??
I don’t know the question. Can you upload both?
Will it not be enough to do dfs and go in once all the edges coming in a particular node is visited? Because the graph is acyclic? Correct me if I am worng.