题意：给你a+b和a*b的值，求a^n+b^n
思路：
因为是膜2^64，所以直接开unsigned long long 就行
代码：
#include<iostream> #include<cstdio> #include<cstring> using namespace std; typedef unsigned long long ll; int n, m; struct node { ll s[3][3]; node() {} node(ll s1, ll s2, ll s3, ll s4) { s[1][1] = s1; s[1][2] = s2; s[2][1] = s3; s[2][2] = s4; } }; node mul(node a, node b) { node t; memset(t.s, 0, sizeof(t.s)); for(int i = 1; i <= 2; i++) for(int j = 1; j <= 2; j++) for(int k = 1; k <= 2; k++) t.s[i][j] = (t.s[i][j]+a.s[i][k]*b.s[k][j]); return t; } node mt_pow(node p, int k) { node q; memset(q.s, 0, sizeof(q.s)); for(int i = 1; i <= 2; i++) q.s[i][i] = 1; while(k) { if(k%2) q = mul(p, q); p = mul(p, p); k /= 2; } return q; } int main(void) { int t, ca = 1; cin >> t; while(t--) { ll p, q; int n; scanf("%llu%llu%d", &p, &q, &n); node base = node(p, 1, -q, 0); printf("Case %d: ", ca++); ll f1 = p; ll f2 = p*p-2*q; if(n == 0) puts("2"); else if(n == 1) printf("%llu\n", f1); else if(n == 2) printf("%llu\n", f2); else { node ans = mt_pow(base, n-2); printf("%llu\n", f2*ans.s[1][1]+f1*ans.s[2][1]); } } return 0; }
