# LOJ 1070 Algebraic Problem

xiaoxiao2021-02-28  9

# LOJ 1070 Algebraic Problem

## Problem Description

Given the value of a+b and ab you will have to find the value of an+bn . a and b not necessarily have to be real numbers.

## Input

Input starts with an integer T (≤ 10000), denoting the number of test cases.

Each case contains three non-negative integers, p, q and n. Here p denotes the value of a+b and q denotes the value of ab. 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 test case, print the case number and (an+bn) modulo 264 .

2 10 16 2 7 12 3

## Sample Output

Case 1: 68 Case 2: 91

### 题意：

#### AC代码：

#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <algorithm> #include <iostream> #include <locale> #include <vector> #include <string> #include <iomanip> #include <cstdio> #include <cstring> #include <stack> #include <queue> #include <map> #include <set> #include <functional> using namespace std; int nnn=2; struct juzhen { unsigned long long x[3][3]; }e,a,b,t; juzhen multi(juzhen A,juzhen B) { juzhen c; memset(c.x,0,sizeof(c.x)); for(int i=1; i<=nnn; i++) for(int j=1; j<=nnn; j++) for(int k=1; k<=nnn; k++) c.x[i][j]+=A.x[i][k]*B.x[k][j]; return c; } juzhen quick(unsigned long long nn) { juzhen A=a,B=e; while(nn>0) { if(nn&1) B=multi(B,A); nn>>=1; A=multi(A,A); } return B; } int main() { int T; scanf("%d",&T); for(int i=1; i<=T; i++) { unsigned long long p,q,n; scanf("%llu%llu%llu",&p,&q,&n); memset(e.x,0,sizeof(e.x)); memset(a.x,0,sizeof(a.x)); memset(b.x,0,sizeof(b.x)); for(int j=1;j<=nnn;j++) e.x[j][j]=1; a.x[1][1] = p; a.x[1][2] = -q; a.x[2][1] = 1; b.x[1][1] = p; b.x[2][1] = 2; if(!n) { printf("Case %d: 2\n",i); continue; } t=quick(n-1); t=multi(t,b); printf("Case %d: %llu\n",i,t.x[1][1]); } return 0; }