HDU4565

题意：

给出a，b，n，m，求$S_n=\lceil(a+\sqrt b)^n\rceil\%m$。其中$0<a,m<2^{15}$，$(a-1)^2<b <a^2$，$0<b,n<2^{31}$。

思路：

首先根据构造共轭因式的思想，构造下式：

$$(a+\sqrt b)^n=A+B\sqrt b$$ $$(a-\sqrt b)^n=A-B\sqrt b$$

注意一个条件，$(a-1)^2<b <a^2$，则$a-1<\sqrt b<a$，则$0<a-\sqrt b<1$，则有$0<(a-\sqrt b)^n=A-B\sqrt b<1$,

则$A -1<B\sqrt b<A​$，

因为$S_n=\lceil(a+\sqrt b)^n\rceil\%m=\lceil(A+B\sqrt b)\rceil\%m=2*A$。

①和②相加得$(a+\sqrt b)^n+(a-\sqrt b)^n=2*A$。

所以$S_n=(a+\sqrt b)^n+(a-\sqrt b)^n$。

对于$S_n$的递推公式，可以有多种方法推导得到，这里说其中两种。

法一：二阶线性递推式

定理：对于由递推公式$a_{n+2}=pa_{n+1}+qa_n$，$a_1=\alpha,a_2=\beta$给出的数列$\left\{a_n\right\}$，方程$x^2-px-q=0$，叫做数列$\left\{a_n\right\}$的特征方程。

这里$(a+\sqrt b)^n$和$(a-\sqrt b)^n$是特征方程的两个根，可以由韦达定理推出特征方程为$x^2-2ax+a^2-b=0$，所以有递推公式$S_{n+2}=2a*S_{n+1}+(b-a^2)*S_n$。

法二：递推

$$\ \ \ \ S_n*[(a+\sqrt b)+(a-\sqrt b)]\\=[(a+\sqrt b)^n+(a-\sqrt b)^n][(a+\sqrt b)+(a-\sqrt b)]\\=(a+\sqrt b)^{n+1}+(a-\sqrt b)^{n+1}+(a^2-b)(a+\sqrt b)^{n-1}+(a^2-b)(a-\sqrt b)^{n-1}\\=S_{n+1}+(a^2-b)*S_{n-1}$$

所以$S_{n+1}=2a*S_n+(b-a^2)*S_{n-1}$。

这样就可以构造矩阵了，

$$\left( \begin{matrix} f_n \\ f_{n-1} \\ \end{matrix} \right) =\left( \begin{matrix} 2a & b-a^2\\ 1 & 0\\ \end{matrix} \right) =\left( \begin{matrix} f_{n-1} \\ f_{n-2} \\ \end{matrix} \right)$$ $$\left( \begin{matrix} f_n \\ f_{n-1} \\ \end{matrix} \right) =\left( \begin{matrix} 2a & b-a^2\\ 1 & 0\\ \end{matrix} \right)^{n-1} =\left( \begin{matrix} f_1 \\ f_2 \\ \end{matrix} \right)$$

再用矩阵快速幂做就可以了。

这里要注意，$b-a^2$可能是负的，所以在矩阵乘法中取模的时候要加上模数再取模。

代码：

typedef long long ll;
struct mat
{
    long long a[2][2];
}m,r;
ll p;
mat mult(mat x,mat y)
{
    mat res={0};
    int i,j,k;
    for(i=0;i<2;i++)
        for(j=0;j<2;j++)
            for(k=0;k<2;k++)
                res.a[i][j]=(res.a[i][j]+(x.a[i][k]*y.a[k][j])%p+p)%p;
    return res;
}
mat PowerMod(mat x,long long n)
{
    mat ans={0};
    int i;
    for(i=0;i<2;i++)
        ans.a[i][i]=1;
    while(n>0)
    {
        if(n%2==1)
            ans=mult(ans,x);
        x=mult(x,x);
        n=n/2;
    }
    return ans;
}
int main()
{
    ll x,y,n;
    while(scanf("%lld%lld%lld%lld",&x,&y,&n,&p)!=EOF)
    {
        m.a[0][0]=2*x;m.a[0][1]=y-x*x;
        m.a[1][0]=1;m.a[1][1]=0;
        r=PowerMod(m,n-1);
        ll ans=(r.a[0][0]*2*x+r.a[0][1]*2)%p;
        printf("%lld\n",ans);
    }
    return 0;
}

HDU5451

题意：

给出x和一个质数M，$y=(5+2\sqrt 6)^{1+2^x}$，求$\lfloor y\rfloor\%m$。其中$0≤x≤2^{32}$，$M≤46337$。

思路：

类似上题的方法，根据特征方程可以求出递推公式为$f_n=10*f_{n-1}-f_{n-2}$。

已知数列$\left\{a_n\right\}​$满足$a_{n+2}=c_1*a_{n+1}+c_2*a_n​$，其中$c_1​$，$c_2​$为常数，且$c_2≠0​$，$n∈N^*​$。

定理1：方程$x^2=c_1x+c_2$为该式的特征的特征方程，该方程的根称为$\left\{a_n\right\}$的特征根，记为$\lambda_1$，$\lambda_2$。

定理2:若$\lambda_1≠\lambda_2$，则$a_n=b_1{\lambda_1}^n+b_2{\lambda_2}^n$，其中$b_1$，$b_2$为常数，且满足

$$\left\{ \begin{array}{c} a_1=b_1\lambda_1+b_2\lambda_2 \\ a_2=b_1{\lambda_1}^2+{b_2\lambda_2}^2 \\ \end{array} \right.$$

定理3:若$\lambda_1=\lambda_2=\lambda$，则$a_n=(b_1+b_2n)\lambda^n$，其中$b_1$，$b_2$为常数，且满足

$$\left\{ \begin{array}{c} a_1=(b_1+b_2)\lambda \\ a_2=(b_1+2b_2)\lambda \\ \end{array} \right.$$

由定理2，得到通项$f_n=(5+2\sqrt 6)^n+(5-2\sqrt 6)^n$。

因为$(5+2\sqrt6)^n>1$，$(5-2\sqrt6)^n<1$，因$(5+2\sqrt 6)^n$的整数部分为$f_n-1$。

指数是$2^x+1$非常大，但模数$M≤46337$，所以可以直接暴力找循环节。

还有一个结论，对于广义斐波那契数列$f(n)=af(n−1)+bf(n−2),f(1)=c,f(2)=d$，

f(n)%p循环节：当c是模p的二次剩余，枚举$n=(p-1)$的因子， 　　　　　　　当c是模p的非二次剩余，枚举$n=(p-1)(p+1)$的因子。

什么叫二次剩余呢？

d是模p的二次剩余当且仅当$d(p−1)/2≡1(mod\ p)$，

d是模p的非二次剩余当且仅当$d(p−1)/2≡-1(mod\ p)$。

假设MOD为模数,则在$f[2]!=MOD$时,$(MOD+1)*(MOD-1)$一定为其一个循环节。

在这里循环节可以直接算出，循环节为$(m+1)*(m-1)$。

代码：

typedef long long ll;
ll f[100010];
ll l[100010];
int init(ll m)
{
    f[0]=2%m,f[1]=10%m;
    for(int i=2;;i++)
    {
        f[i]=(10*f[i-1]-f[i-2]+m)%m;
        //if(i<=10)printf("%lld ",f[i]);
        if(f[i-1]==f[0]&&f[i]==f[1])
            return i-1;
    }
    //printf("\n");
}
long long PowerMod(long long a,long long b,long long c)
{
    long long ans=1;
    long long k;
    k=a;
    k=k%c;
    while(b>0)
    {
        if(b&1)
        ans=(ans*k)%c;
        b>>=1;
        k=(k*k)%c;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    for(int kase=1;kase<=t;kase++)
    {
        ll x,m;
        scanf("%lld%lld",&x,&m);
        int len=init(m);
        //printf("%d\n",len);
        int p=PowerMod(2,x,len);
        //printf("p:%d\n",p);
        printf("Case #%d: %lld\n",kase,(f[(p+1)%len]-1+m)%m);
    }
    return 0;
}