UVa 10655 n次方之和（矩阵快速幂）

题意：

输入非负整数p，q，n，求a^n+b^n的值，其中a和b满足a+b=p，ab=q。

思路：

递推式转化成矩阵的规律：

这道题目根据递推式是可以转化为矩阵的：

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<queue>
 7 #include<cmath>
 8 #include<map>
 9 using namespace std;
10 
11 typedef long long LL;
12 
13 LL p,q,n;
14 
15 struct Matrix
16 {
17     LL m[2][2];
18 }ans,base;
19 
20 Matrix multi(Matrix a,Matrix b)
21 {
22     Matrix temp;
23     for(int i=0;i<2;i++)
24     for(int j=0;j<2;j++)
25     {
26         temp.m[i][j]=0;
27        for(int k=0;k<2;k++)
28        {
29           temp.m[i][j]=(temp.m[i][j]+a.m[i][k]*b.m[k][j]);
30        }
31     }
32     return temp;
33 }
34 
35 void pow(int x)
36 {
37     ans.m[0][0]=ans.m[1][1]=1;
38     ans.m[0][1]=ans.m[1][0]=0;
39     base.m[0][0]=0;
40     base.m[0][1]=1;
41     base.m[1][0]=-q;
42     base.m[1][1]=p;
43     while(x)
44     {
45         if(x&1)
46         {
47             ans=multi(ans,base);
48         }
49         base=multi(base,base);
50         x>>=1;
51     }
52     printf("%lld
",ans.m[1][1]*p+2*ans.m[1][0]);
53 }
54 
55 int main()
56 {
57     //freopen("D:\input.txt","r",stdin);
58     while(scanf("%lld%lld%lld",&p,&q,&n)==3)
59     {
60         if(n==0)   {puts("2");continue;}
61         if(n==1)   {printf("%lld
",p);continue;}
62         if(n==2)   {printf("%lld
",p*p-2*q);continue;}
63         pow(n-1);
64     }
65     return 0;
66 }