uva10655

Given the value of a+b and ab you will have to find the value of a n + b n 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 p denotes 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 a n + b n. You can always assume that a n + b n fits in a signed 64-bit integer. Sample Input 10 16 2 7 12 3 0 0 Sample Output 68 91

矩阵快速幂。。。

很明显，要把a和b解出来很困难，因为还有虚数，讨论很烦

那么我们就要转化一下用p和q解决问题

我们先用a^(n-1)+b^(n-1)推出a^n+b^n

要想升幂，还是生一次只能乘a+b,但是会多出来两项（在纸上写一下，这里不方便打公式）

中间的两项提出一个a*b，变成了a^(n-2)+b^(n-2) 那么我们就可以递推了

但是太慢了，就用矩阵快速幂。。。

构造矩阵就行了

注意特判n==0

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

struct mat {

    ll a[][];

} A, B;

ll p, q, n;

mat operator * (mat A, mat B)

{

    mat ret; memset(ret.a, , sizeof(ret.a));

    for(int i = ; i < ; ++i)

        for(int j = ; j < ; ++j)

            for(int k = ; k < ; ++k) ret.a[i][j] = ret.a[i][j] + A.a[i][k] * B.a[k][j];

    return ret;

}

mat power(mat A, ll t)

{

    mat ret; memset(ret.a, , sizeof(ret.a));

    for(int i = ; i < ; ++i) ret.a[i][i] = ;

    for(; t; t >>= , A = A * A) if(t & ) ret = ret * A;

    return ret;

}

int main()

{

    while(scanf("%lld%lld%lld", &p, &q, &n) == )

    {

        if(n == ) { puts(""); continue; }

        if(n == ) { printf("%lld\n", p); continue; }

        if(n == ) { printf("%lld\n", p * p -  * q); continue; }

        A.a[][] = p; A.a[][] = -q;

        A.a[][] = ; A.a[][] = ;

        B.a[][] = p * p -  * q; B.a[][] = p;

        B = power(A, n - ) * B;

        printf("%lld\n", B.a[][]);

    }

    return ;

}

巴特西

uva10655

最新文章

热门文章