【HDU3117】Fibonacci Numbers
题面
求斐波那契数列的第\(n\)项的前四位及后四位。
其中\(0\leq n<2^{32}\)
题解
前置知识：线性常系数齐次递推
其实后四位还是比较好求，矩阵快速幂就可以了，主要是前四位。
先用线性常系数齐次递推求出斐波那契数列的通项公式
\[f_n=\frac{\sqrt 5}{5}\left((\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n\right)
\]
\]
因为数列的前\(39\)项我们还是存的下的，所以我们只考虑\(n\geq40\)的情况
考虑到\(n\geq40\)时\(\frac{\sqrt 5}{5}*(\frac{1-\sqrt5}{2})^n\)是个很小的东西，可以不考虑它的影响
那么我们就是要求
\[\frac{\sqrt 5}{5}(\frac{1+\sqrt5}{2})^n
\]
\]
现在先考虑这样一个式子，数\(x\)用科学计数法表示
\[x=t*10^k
\]
\]
那么\(x\)的前四位即为\(t\)的前四位，我们将\(x\)取个常用对数
\[\lg x=\lg t+k
\]
\]
类比上式以及我们要求的式子：
\[\begin{aligned}
y&=\lg\left(\frac{\sqrt 5}{5}(\frac{1+\sqrt5}{2})^n\right)\\
&=\lg\frac{\sqrt 5}{5}+\lg\;(\frac{1+\sqrt5}{2})^n\\
&=\lg\frac{\sqrt 5}{5}+n\times \lg\frac{1+\sqrt5}{2}
\end{aligned}
\]
y&=\lg\left(\frac{\sqrt 5}{5}(\frac{1+\sqrt5}{2})^n\right)\\
&=\lg\frac{\sqrt 5}{5}+\lg\;(\frac{1+\sqrt5}{2})^n\\
&=\lg\frac{\sqrt 5}{5}+n\times \lg\frac{1+\sqrt5}{2}
\end{aligned}
\]
那么\(\lg t=y-\lfloor y\rfloor\)，最后\(1000\times 10^y\)的整数部分就是答案。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int Mod = 1e4;
struct Matrix {
int m[2][2];
Matrix() { memset(m, 0, sizeof(m)); }
void init() { for (int i = 0; i < 2; i++) m[i][i] = 1; }
int *operator [] (int id) { return m[id]; }
Matrix operator * (const Matrix &b) {
Matrix res;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++)
res[i][j] = (res[i][j] + m[i][k] * b.m[k][j] % Mod) % Mod;
return res;
}
} ;
int N, f[40];
int TASK1() {
double s = log10(sqrt(5.0) / 5.0) + 1.0 * N * log10((1.0 + sqrt(5.0)) / 2.0);
s = s - (int)s;
double ans = 1000 * pow(10.0, s);
return ans;
}
int TASK2() {
Matrix S, T, ans; int n = N; ans.init();
S[0][0] = 1;
T[0][0] = 1, T[0][1] = 1;
T[1][0] = 1, T[1][1] = 0;
while (n) { if (n & 1) ans = ans * T; n >>= 1; T = T * T; }
S = ans * S;
return ans[1][0];
}
int main () {
f[0] = 0, f[1] = 1; for (int i = 2; i < 40; i++) f[i] = f[i - 1] + f[i - 2];
while (~scanf("%d", &N)) {
if (N < 40) { printf("%d\n", f[N]); continue; }
printf("%04d...%04d\n", TASK1(), TASK2());
}
return 0;
}