S5來襲4/11旗艦上市直擊★美車模手癢不小心...法人:14檔今年本業虧定了老伯送飲料 遭學生糾察...
2012-12-15 18:51:35 人氣(63) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][math] 10655 - Contemplation - Algebra

0
收藏
0
推薦

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 an+bn

 

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 00.

 

Output

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

 

Sample Input                               Output for Sample Input

10 16 2
7 12 3
0 0

68

91 

 


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;
}

10655Contemplation - Algebra
台長:Morris
人氣(63) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][解一][spfa+窮舉] 11090 - Going in Cycle!!
此分類上一篇:[UVA][半高斯] 10524 - Matrix Reloaded

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文