LOJ 1070 Algebraic Problem
题目链接：Light OJ 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 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
题意：
给出p=a+b的值和q=ab的值，求
(an+bn)
%
264
,(p,q,n都是32位有符号的数)
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;
}
