首先附上题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=5667 题目分析 像这种递推公式的问题,n很大的时候,常用的处理方法是矩阵快速幂,但是这个好像很难构造。 博主思路如下:取对数 设k(i) = loga(f(i)) 那么 根据推导 k(1) = loga(1)=0 k(2) = loga(ab) = b k(i) = b + c*k(i-1)+k(i-2) 那么可以用矩阵快速幂的方式 求解 k(n) f(n) = ak(n)再通过整数快速幂的方式求解。 还有一个问题:k(n)很大 直接求幂肯定连int64_t都要溢出 那么运用费马小