Problem: Fibonacci with GCD
Editorial: It's a segment tree problem with simple matrix exponentiation for generating fibonacci numbers. In this problem, we will be given some numbers. Then we will be asked to perform some queries. Each query there will be a range, from that range we need to find GCD of all the elements fibonacci numbers. Say for 2 4 8, we need to calculate GCD ( fib[2], fib[4], fib[8] ) = GCD ( 1, 3, 21 ) = 1.
We will create a segment tree, where we will store the gcd of every elements of the array. Basically our segment tree will be made of calculating gcd for a given range. Then for the query we will calculate part by part in the range for our gcd. If left and right both child node is -1, then we will simply return 1. If left child is -1 but right child has positive value, then we will return right child. Similarly we will do for the right child being -1 also. And when both the child have positive value, we will return the gcd between them. After getting the gcd value from the elements of the range from our query, then we will find the fibonacci number of that gcd value. We will do that with matrix exponentiation.
So, basically, for this problem, we will create segment tree first with corresponding gcd, and then after the query, we will calculate the fibonacci number. Say for values : 2, 4, 8, the GCD = 1. So our answer will be fibonacci [ 1 ] and that is 1. ( Fibonacci series : 1, 2, 3, 5,....).
Editorial: It's a segment tree problem with simple matrix exponentiation for generating fibonacci numbers. In this problem, we will be given some numbers. Then we will be asked to perform some queries. Each query there will be a range, from that range we need to find GCD of all the elements fibonacci numbers. Say for 2 4 8, we need to calculate GCD ( fib[2], fib[4], fib[8] ) = GCD ( 1, 3, 21 ) = 1.
We will create a segment tree, where we will store the gcd of every elements of the array. Basically our segment tree will be made of calculating gcd for a given range. Then for the query we will calculate part by part in the range for our gcd. If left and right both child node is -1, then we will simply return 1. If left child is -1 but right child has positive value, then we will return right child. Similarly we will do for the right child being -1 also. And when both the child have positive value, we will return the gcd between them. After getting the gcd value from the elements of the range from our query, then we will find the fibonacci number of that gcd value. We will do that with matrix exponentiation.
So, basically, for this problem, we will create segment tree first with corresponding gcd, and then after the query, we will calculate the fibonacci number. Say for values : 2, 4, 8, the GCD = 1. So our answer will be fibonacci [ 1 ] and that is 1. ( Fibonacci series : 1, 2, 3, 5,....).
No comments:
Post a Comment