Contemplation! Algebra 矩阵快速幂

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

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<queue>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<string>

using namespace std;

typedef long long  LL;

typedef unsigned long long ULL;

#define MAXN 49

#define MOD 10000007

#define INF 1000000009

const double eps = 1e-;

/*

矩阵快速幂！

an = p an - q an-1

*/

LL p, q, n;

struct Mat

{

    Mat()

    {

        memset(a, , sizeof(a));

    }

    LL a[][];

    Mat operator * (const Mat& rhs)

    {

        Mat ret;

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

        {

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

            {

                if (a[i][j])

                {

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

                        ret.a[i][k] += a[i][j] * rhs.a[j][k];

                }

            }

        }

        return ret;

    }

};

Mat fpow(Mat m, LL b)

{

    Mat tmp = m, ans;

    ans.a[][] = ans.a[][] = ;

    while (b != )

    {

        if (b & )

            ans = tmp * ans;

        tmp = tmp * tmp;

        b /= ;

    }

    return ans;

}

int main()

{

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

    {

        LL a1 = p, a2 = p*p -  * q;

        if (n == )

            printf("2\n");

        else if (n == )

            printf("%lld\n", a1);

        else if (n == )

            printf("%lld\n", a2);

        else

        {

            n = n - ;

            Mat M;

            M.a[][] = p, M.a[][] = -q, M.a[][] = ;

            M = fpow(M, n);

            printf("%lld\n", M.a[][] * a2 + M.a[][] * a1);

        }

    }

}

巴特西

Contemplation! Algebra 矩阵快速幂

最新文章

热门文章