首页 > 代码库 > [HDOJ5451]Best Solver(乱搞)

[HDOJ5451]Best Solver(乱搞)

题目:http://acm.hdu.edu.cn/showproblem.php?pid=5451

分析:A=5+2根号6 B=6-2根号6

       n=1+2^x

      那么A^n+B^n是整数

      注意到0<B^n<1

      所以ans=A^n+B^n-1

      这个结果形式和斐波那契通项结构很像

      于是构造an=p*an-1+q*an-2

      反特征根得到递推式子an=10*(an-1) - (an-2)

      n过于大,于是无法矩阵快速幂

      注意M很小,于是模出来的肯定是有循环节的,循环节最大也是M*M,可以承受

      最后就是1+2^x膜循环节的问题了,快速幂解决

[HDOJ5451]Best Solver(乱搞)