HDU 4565 So Easy! 解題報告

題目

比賽

題意：給出a，b，n，m，求

的Sn。

思路：留意資料範圍(a-1)^2<b<a^2，可知0<a-√b<1，不難想到(a+√b)^n+(a-√b)^n的和為整數，而0<(a-√b)^n<1，是以Sn=[(a+√b)^n+(a-√b)^n]%m，

           已知Sn的通項公式了，如果我們能求出它的遞推公式，就能用矩陣乘法解決了。

           易知特征根為r1=a+√b，r2=a-√b，是以特征方程為r^2-(r1+r2)r+r1*r2=0，即r^2-2a*r+(a^2-b)=0，

           是以Sn的遞推公式為Sn=2a*Sn-1+(b-a^2)*Sn-2。

        然後就構造矩陣：

           初始值S1=(a+√b)%m，S2=2*(a^2+b)，于是這道題就變成矩陣乘法了。

代碼：

//time:140ms
//memeroy:360KB
//length:1520B
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define MAXN 110
#define FI first
#define SE second
using namespace std;

long long toz(long long n,long long mod)
{
    if(n>0) return n%mod;
    else    return mod-(-n)%mod;
}
void mul(long long a[2][2],long long b[2][2],long long mod)
{
    long long tmp[2][2]={{0}};
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
            for(int k=0;k<2;++k)
                tmp[i][j]=(tmp[i][j]+a[i][k]*b[k][j])%mod;
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
            a[i][j]=tmp[i][j];
}
void pow_mod(long long a[2][2],long long p,long long mod)
{
    long long ans[2][2]={{0}};
    ans[0][0]=ans[1][1]=1;
    while(p)
    {
        if(p&1) mul(ans,a,mod);
        mul(a,a,mod);
        p>>=1;
    }
    for(int i=0;i<2;++i)
        for(int j=0;j<2;++j)
            a[i][j]=ans[i][j];
}
int main()
{
    //freopen("/home/moor/Code/input.txt","r",stdin);
    long long  a,b,n,m,c,a1,a2;

    while(cin>>a>>b>>n>>m)
    {
        long long num[2][2];
        c=toz(-a*a+b,m);
        num[0][0]=2*a%m,num[0][1]=1;
        num[1][0]=c,num[1][1]=0;
        a1=(long long )ceil(a+sqrt(b*1.0))%m;
        a2=(2*a*a+2*b)%m;
        if(n>=3)
        {
            pow_mod(num,n-2,m);
            long long tmp[2][2]={{0}};
            tmp[0][0]=a2,tmp[0][1]=a1;
            mul(tmp,num,m);
            cout<<tmp[0][0]<<'\n';
        }
        else    cout<<(n==1?a1:a2)<<'\n';
    }
    //return 0;
}