HDU 4565So Easy!2012長沙邀請賽A題（共轭構造+矩陣的快速冪）

So Easy!
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 910    Accepted Submission(s): 247

Problem Description
　　A sequence Sn is defined as:

Where a, b, n, m are positive integers.┌x┐is the ceil of x. For example, ┌3.14┐=4. You are to calculate Sn.
　　You, a top coder, say: So easy!

Input
　　There are several test cases, each test case in one line contains four positive integers: a, b, n, m. Where 0< a, m < 215, (a-1)2< b < a2, 0 < b, n < 231.The input will finish with the end of file.
 

Output
　　For each the case, output an integer Sn.
 

Sample Input
2 3 1 2013
2 3 2 2013
2 2 1 2013

Sample Output
4
14
4

                   題目大意：題目意思很好懂，主要是小數的n次方不好處理，如果簡單的將整數小數隔離開來，然後對整數對m求余。會有漏洞，前面的數據再乘上後面的小數會產生新的數字，對結果有影響。

           解題思路：下來之後看了下題解，都是直接找一個共轭的(a-sqrt(b))^n一加便組成了整數。以前一直以為共轭只能存在於復數中。a+bi與a-bi共轭之類的。看來還要請教一下自己的高中老師。

           下面是自己的推論，組成了整數之後一切都好辦了，然後往下推，可以得到一個間接遞推公式，然後轉化成矩陣。

快速冪的思想：我也是第一次用這個，所以說下感想，主要是普通的遞推或者直接矩陣轉換超時。所以用快速冪來求解。比如某個矩陣的31次方，可以寫成(1+2*(1+2*(1+2*(1+2)))),只需要八次左右的運算，就可以了，首先31&1=1，那麼就分解一個1出來，然後p*ret，然後就變成了偶數30，將p矩陣變成p^2，n變成15,&1=1直接用p*ret這時候p已經是p^2了，如此反復最後便可以把它求出來。  和求一個數的快速冪是一樣的原理。
           

           題目地址：So Easy!

AC代碼：

#include<iostream>
#include<cmath>
#include<cstring>
#include<string>
#include<cstdio>
using namespace std;
__int64 a,b,n,m;
__int64 ret[2][2],p[2][2],tmp[2][2];

void init()
{
    ret[0][0]=2*a;
    ret[0][1]=-(a*a-b);
    ret[1][0]=1;
    ret[1][1]=0;
    p[0][0]=2*a;
    p[0][1]=-(a*a-b);
    p[1][0]=1;
    p[1][1]=0;
}

void cal1()   //矩陣的平方！&1
{
    int i,j,k;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
        {
            tmp[i][j]=p[i][j];
            p[i][j]=0;
        }

    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
          for(k=0;k<2;k++)
            p[i][j]=((p[i][j]+tmp[i][k]*tmp[k][j])%m+m)%m;
}

void cal2()   //矩陣的乘法&1
{
    int i,j,k;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
        {
             tmp[i][j]=ret[i][j];
             ret[i][j]=0;
        }

    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
          for(k=0;k<2;k++)
            ret[i][j]=((ret[i][j]+tmp[i][k]*p[k][j])%m+m)%m;
}

void fastmi()
{
    n-=2;
    while(n)
    {
        if(n&1)
        {
            cal2();
            n--;
        }
        else
        {
            cal1();
            n>>=1;
        }
    }
}

int main()
{

    while(~scanf("%I64d%I64d%I64d%I64d",&a,&b,&n,&m))
    {
        if(n==1)
        {
            printf("%I64d\n",2*a%m);
            continue;
        }
        init();
        fastmi();
        //C1=2*a  C0=2
        printf("%I64d\n",((ret[0][0]*2*a+ret[0][1]*2)%m+m)%m);
    }
    return 0;
}