10655 - Contemplation - Algebra

Problem E
Contemplation! Algebra
Input: Standard Input

Output: Standard Output

Time Limit: 1 Second

Given the value of a+b and ab you will have to find the value of aⁿ+bⁿ

Input

The input file contains several lines of inputs. Each line except the last line contains 3 non-negative integers p, q and n. Here pdenotes the value of a+b and q denotes the value of ab. Input is terminated by a line containing only two zeroes. This line should not be processed. Each number in the input file fits in a signed 32-bit integer. There will be no such input so that you have to find the value of 0⁰.

Output

For each line of input except the last one produce one line of output. This line contains the value of aⁿ+bⁿ.  You can always assume that aⁿ+bⁿ fits in a signed 64-bit integer.

Sample Input                               Output for Sample Input

10 16 2

7 12 3

0 0

Problem setter: Shahriar Manzoor, Member of Elite Problemsetters' Panel

Special Thanks: Mohammad Sajjad Hossain
 

f(n) = p*f(n-1) - q*f(n-2)

A = [0 -q]
    [1  p]

#include <stdio.h>
struct mtx {
    long long v[2][2];
} I2 = {1,0,0,1}, A = {0,1,1,1};
mtx mult(mtx x, mtx y) {
    int i, j, k;
    mtx z = {0,0,0,0};
    for(i = 0; i < 2; i++)
        for(j = 0; j < 2; j++)
            for(k = 0; k < 2; k++)
                z.v[i][k] += x.v[i][j]*y.v[j][k];
    return z;
}
int main() {
    long long p, q, n;
    while(scanf("%lld %lld %lld", &p, &q, &n) == 3) {
        A.v[0][1] = -q, A.v[1][1] = p;
        mtx x = I2, y = A;
        x.v[0][0] = p;
        x.v[0][1] = p*p-2*q;
        x.v[1][0] = p*p-2*q;
        x.v[1][1] = p*p*p-3*p*q;
        if(n == 0) {
            puts("2");
            continue;
        }
        n--;
        while(n) {
            if(n&1)
                x = mult(x, y);
            y = mult(y, y);
            n >>= 1;
        }
        printf("%lld\n", x.v[0][0]);
    }
    return 0;
}