[HDU - 2256] Problem of Precision(矩阵快速幂)

Input

The first line of input gives the number of cases, T. T test cases follow, each on a separate line. Each test case contains one positive integer n. (1 <= n <= 10^9) 

Output

For each input case, you should output the answer in one line. 

Sample Input

3
1
2
5

Sample Output

9
97
841

解析

这题不能直接(an+bn*sqrt(6))%1024，精度导致误差。（我一开始做法也是这样...）

然后通过推导得到矩阵关系，最后一步记得向下取整。

（向下取整：n减了一个特别小的数去取整就是n-1）

（图片转自其他博客  有水印...过程也比较详细）

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <cmath>
#define mod 1024
using namespace std;
struct map
{
    double a[2][2];
};
map quickpow(map x,map y)
{
    map b;
    memset(b.a,0,sizeof(b.a));
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
        for(int k=0;k<2;k++)
        b.a[i][j]=fmod(b.a[i][j]+fmod(x.a[i][k]*y.a[k][j],mod),mod);
    return b;
}
double getres(int n)
{
    map c,b,res;
    b.a[0][0]=b.a[1][1]=1,b.a[0][1]=b.a[1][0]=0;
    c.a[0][0]=5,c.a[0][1]=2,c.a[1][0]=12,c.a[1][1]=5;
    while(n)//快速幂
    {
        if(n&1) b=quickpow(b,c);
        c=quickpow(c,c);//矩阵相乘
        n>>=1;
    }
    res.a[0][0]=5,res.a[0][1]=2,res.a[1][1]=res.a[1][0]=0;
    res=quickpow(res,b);
    return fmod(2.0*res.a[0][0]-1,mod);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        if(n==1)
            printf("9\n");
        else    printf("%d\n",(int)getres(n-1)%mod);
    }
    return 0;
}