首页 > 代码库 > HDU 3117 Fibonacci Numbers(斐波那契前后四位,打表+取对+矩阵快速幂)
HDU 3117 Fibonacci Numbers(斐波那契前后四位,打表+取对+矩阵快速幂)
HDU 3117 Fibonacci Numbers(斐波那契前后四位,打表+取对+矩阵快速幂)
ACM
题目地址:HDU 3117 Fibonacci Numbers
题意:
求第n个斐波那契数的前四位和后四位。
不足8位直接输出。
分析:
前四位有另外一题HDU 1568,用取对的方法来做的。
后四位可以用矩阵快速幂,MOD设成10000就行了。
代码:
/* * Author: illuz <iilluzen[at]gmail.com> * Blog: http://blog.csdn.net/hcbbt * File: 3117.cpp * Create Date: 2014-08-04 10:25:26 * Descripton: */ #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define repf(i,a,b) for(int i=(a);i<=(b);i++) typedef long long ll; const int N = 41; const int SIZE = 2; // max size of the matrix const int MOD = 10000; ll n; ll tab[N]; double ans; struct Mat{ int n; ll v[SIZE][SIZE]; // value of matrix Mat(int _n = SIZE) { n = _n; memset(v, 0, sizeof(v)); } void init(ll _v) { repf (i, 0, n - 1) v[i][i] = _v; } void output() { repf (i, 0, n - 1) { repf (j, 0, n - 1) printf("%lld ", v[i][j]); puts(""); } puts(""); } } a, b; Mat operator * (Mat a, Mat b) { Mat c(a.n); repf (i, 0, a.n - 1) { repf (j, 0, a.n - 1) { c.v[i][j] = 0; repf (k, 0, a.n - 1) { c.v[i][j] += (a.v[i][k] * b.v[k][j]) % MOD; c.v[i][j] %= MOD; } } } return c; } Mat operator ^ (Mat a, ll k) { Mat c(a.n); c.init(1); while (k) { if (k&1) c = a * c; a = a * a; k >>= 1; } return c; } double fib(int x) { return -0.5 * log(5.0) / log(10.0) + ( (double)n) * log((sqrt(5.0) + 1) / 2) / log(10.0); } void table() { // table tab[0] = 0; tab[1] = 1; repf (i, 2, 40) tab[i] = tab[i - 1] + tab[i - 2]; } void pre4(int n) { ans = fib(n); ans -= floor(ans); ans = pow(10.0, ans); while (ans < 1000) ans *= 10; printf("%d", (int)ans); } void last4(int n) { a.init(0); a.v[0][0] = a.v[0][1] = a.v[1][0] = 1; b = a ^ (n - 1); printf("%04lld\n", b.v[0][0]); } int main() { table(); while (~scanf("%lld", &n)) { if (n < 40) { printf("%lld\n", tab[n]); continue; } pre4(n); printf("..."); last4(n); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。