本文主要是介绍NOIP模拟(10.23)T1 Fibonacci,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Fibonacci
题目背景:
分析:暴力
最大只要109,如果你稍微观察一下就会发现,109的fibonacci数少的可怜,因为每一个几乎都是上一个的两倍少一些,然后230 > 109,那么最多也不会超过30的两倍咯······实践证明有45个,那么直接暴力找出所有乘积,每次二分查找给出的x即可······
Source:
/*created by scarlyw
*/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <set>
#include <map>
#include <vector>
#include <queue>const int MAXN = 60;
const int limit = 1000000000;int num, cnt, t, x;
int f[MAXN], a[MAXN * MAXN];inline void pre_work() {f[0] = 0, f[1] = 1;for (int i = 2; ; ++i) {f[i] = f[i - 2] + f[i - 1];if (f[i] > limit) {num = i - 1;break ;}}for (int i = 0; i <= num; ++i)for (int j = 0; j <= num; ++j)if ((long long)f[i] * (long long)f[j] <= limit) a[++cnt] = f[i] * f[j];std::sort(a + 1, a + cnt + 1);
}inline bool binary(int x) {int l = 0, r = cnt + 1;while (l + 1 < r) {int mid = l + r >> 1;if (a[mid] <= x) l = mid;else r = mid;}if (a[l] == x) return true;else return false;
}inline void check(int x) {if (binary(x)) printf("Yes\n");else printf("No\n");
}int main() {
// freopen("fib.in", "r", stdin);
// freopen("fib.out", "w", stdout);scanf("%d", &t), pre_work();while (t--) scanf("%d", &x), check(x);return 0;
}
这篇关于NOIP模拟(10.23)T1 Fibonacci的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!