LightOJ: Algebraic Problem

Problem Link: loj1070
Technique: Matrix Exponentiation

Given the value of a+b and ab you will have to find the value of aⁿ+bⁿ. a and b not necessarily have to be real numbers. I solved this using matrix exponentiation technique. I will now write about how I modelled the base matrix for multiplication. There may be other approaches too. But first please read this mat expo if you don't know about how to create a matrix from a recurrance relation.
First let's observe some cases.

If n = 0, a⁰+b⁰ = 1+1 = 2
If n = 1, a¹+b¹ = a+b - 0
If n = 2, a²+b² = (a+b) (a+b) - 2ab
If n = 3, a³+b³ = (a+b) ( (a+b)² - ab ) - 2ab (a+b)
..............     ..............     .............     .................
So, basically the recurrence somehow turns like this -->
(a¹+b¹) = (a+b) + (-0)
(a²+b²) = (a+b) (a+b) + 2(-ab)
So,

base  =  | (a+b)   -ab  |
             |   1           0   |
We will multiply (a+b) with base [0][0] and 2 with base [0][1], then we will get our final output by summing these two elements.
So, when n = 0 , ans will be 2.
When n = 1, ans will be a+b
When n = 2, ans will be (base)¹  = (a+b) * (a+b) + 2 * (-ab) = (a+b)² - 2ab
When n = 3, ans will be (base)²  = (a+b) * [(a+b)² -ab)] + 2 * [-ab*(a+b)]
Let's see this : (for n = 3)

In our base matrix, after performing exponentiation, at base [0][0] we get [(a+b)² -ab)], and we will multiply it with (a+b). Similarly, at base[0][1] we get [-ab*(a+b)], so we will multuply it with 2. And by summing these two elements, we will get our final output.

NOTE : As For each test case, print the case number and (aⁿ+bⁿ) modulo 2⁶⁴, we will use unsigned long long for each variable instead of applying modulus operation. This will save our time. Infact, without this, the program will get TLE.



"Don't directly copy code. First try to understand how each step works, then do your own coding."