uva 10655 - Contemplation! Algebra (构造矩阵,快速幂)
题意:
给出a+b和ab的值,问a^n+b^n
思路:
构造矩阵,手写一下很显然…
转移矩阵M=[0 , 1]
[-q,p ]
初始矩阵M1=[p ]
[p^2-2*q]
快速幂即可。
有个坑点在于..读入的结束是p=0&q=0,并且只有这两个输入。
如果用p=0&&q=0作为终止条件,那么就会将三个输入,但p==0&&q==0的情况错误得终止…
正确的做法是 while (~scanf("%lld%lld%lld",&p,&q,&n)==3)
1/* ***********************************************
2Author :111qqz
3Created Time :2017年10月01日 星期日 03时01分38秒
4File Name :10655.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define PB push_back
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28
29using namespace std;
30const double eps = 1E-8;
31const int dx4[4]={1,0,0,-1};
32const int dy4[4]={0,-1,1,0};
33const int inf = 0x3f3f3f3f;
34LL p,q,n;
35struct Mat
36{
37 LL mat[105][105];
38 void clear()
39 {
40 ms(mat,0);
41 }
42}M,M1;
43Mat operator * (Mat a,Mat b)
44{
45 Mat c;
46 c.clear();
47 for ( int i = 0 ; i < 2 ; i++)
48 for ( int j = 0 ; j < 2 ; j++)
49 for ( int k = 0 ; k < 2 ; k++)
50 c.mat[i][j] += a.mat[i][k] * b.mat[k][j];
51 return c;
52}
53Mat operator ^ (Mat a,LL b)
54{
55 Mat ret;
56 ret.clear();
57 for ( int i = 0 ; i < 2 ; i++) ret.mat[i][i] = 1LL;
58
59 while (b>0)
60 {
61 if (b&1) ret = ret * a;
62 a = a * a;
63 b = b >> 1LL;
64 }
65 return ret;
66}
67LL solve()
68{
69 if (n==0) return 2LL;
70 if (n==1) return p;
71 if (n==2) return p*p-2*q;
72 M1.clear();
73 M1.mat[0][0] = p;
74 M1.mat[1][0] = p*p-2*q;
75 M.clear();
76 M.mat[0][1] = 1;
77 M.mat[1][0] = -q;
78 M.mat[1][1] = p;
79 Mat ans;
80 ans.clear();
81 ans = (M^(n-2))*M1;
82 return ans.mat[1][0];
83}
84int main()
85{
86 #ifndef ONLINE_JUDGE
87// freopen("./in.txt","r",stdin);
88 #endif
89 while (scanf("%lld%lld%lld",&p,&q,&n)==3)
90 {
91 //if (p==0&&q==0) break;
92 //scanf("%lld",&n);
93 LL ans = solve();
94 printf("%lld\n",ans);
95 }
96
97 #ifndef ONLINE_JUDGE
98 fclose(stdin);
99 #endif
100 return 0;
101}