HDU -- 5451 Best Solver（广义斐波那契数列）

题目vj链接

题面：

题意：
y=(5+26 ​)1+2x,x(0≤x<232)
求：
$\left[y\right]\%M,其中\left[y\right]指y的整数部分，M为\le 46337的质数$[y]%M,其中[y]指y的整数部分，M为≤46337的质数。

题解：
我们设 $A_n=(5+2\sqrt{6}{)}^n,B_n=(5-2\sqrt{6}{)}^n,S_n=A_n+B_n$An​=(5+26 ​)n,Bn​=(5−26 ​)n,Sn​=An​+Bn​

我们可得 $S_n是整数，B_n\le 1,A_n形式与y一致，那么\left[y\right]=S_n-1$Sn​是整数，Bn​≤1,An​形式与y一致，那么[y]=Sn​−1

观察：
$S_n=(5+2\sqrt{6}{)}^n+(5-2\sqrt{6}{)}^n$Sn​=(5+26 ​)n+(5−26 ​)n 类似于斐波那契数列通项公式，猜测其与斐波那契数列具有类似的形式：具有递推式，对一个质数取模有循环节等等。

求解递推式：

合理猜测大法：
$S_0=2,S_1=10,S_2=98$S0​=2,S1​=10,S2​=98，然后我们类比斐波那契数列的递推式， $S_n只与S_{n-1}和S_{n-2}$Sn​只与Sn−1​和Sn−2​有关，得到 $S_n=10\ast S_{n-1}-S_{n-2}$Sn​=10∗Sn−1​−Sn−2​

数学论证：
$S_n=(5+2\sqrt{6}{)}^n+(5-2\sqrt{6}{)}^n$Sn​=(5+26 ​)n+(5−26 ​)n

$S_n=\left(\right(5+2\sqrt{6}{)}^{n-1}+(5-2\sqrt{6}{)}^{n-1})\ast \left(\right(5+2\sqrt{6})+(5-2\sqrt{6}\left)\right)-\left(\right(5+2\sqrt{6}{)}^{n-2}+(5-2\sqrt{6}{)}^{n-2})$Sn​=((5+26 ​)n−1+(5−26 ​)n−1)∗((5+26 ​)+(5−26 ​))−((5+26 ​)n−2+(5−26 ​)n−2)

$S_n=10S_{n-1}-S_{n-2}$Sn​=10Sn−1​−Sn−2​

求解：
既然已经求的递推式，那么可以有一下方法求解此问题。
（1）线性地推，杜教BM。
（2）矩阵快速幂。
（3）M较小，暴力寻找循环节。

代码：暴力找循环节

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=200100;
const int maxm=100100;
const int maxp=100100;
const int up=100100;

int a[maxn];
int mypow(int a,int b,int mod)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}

int main(void)
{
    int t;
    scanf("%d",&t);
    for(int tt=1;tt<=t;tt++)
    {
        int x,mod;
        scanf("%d%d",&x,&mod);
        a[0]=2%mod,a[1]=10%mod;
        int tot=0;
        for(int i=2;i<maxn;i++)
        {
            a[i]=10*a[i-1]-a[i-2]+mod;
            a[i]%=mod;
            if(a[i]==a[1]&&a[i-1]==a[0])
            {
                tot=i-1;
                break;
            }
        }
        ll pp=(1+mypow(2,x,tot)%tot)%tot;
        printf("Case #%d: %d\n",tt,(a[pp]-1+mod)%mod);
    }
    return 0;
}