HDU - 5167 - Fibonacci

小鱼儿 2022-06-12 07:22 112阅读 0赞

--------------------

题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=5167][http_acm.hdu.edu.cn_showproblem.php_pid_5167]

## 题目描述 ##

### Description ###

Following is the recursive definition of Fibonacci sequence:

![此处输入图片的描述][20150810201453839]

Now we need to check whether a number can be expressed as the product of numbers in the Fibonacci sequence.

### Input ###

There is a number (T) shows there are (T) test cases below. (T≤100,000T≤100,000)  
For each test case , the first line contains a integers n , which means the number need to be checked.  
0≤n≤1,000,000,000

### Output ###

For each case output “Yes” or “No”.

### Sample Input ###

3  
4  
17  
233

### Sample Output ###

Yes  
No  
Yes

## 解题思路 ##

斐波那契数列，判断输入的数字是否能用数列中的数相乘表示，  
先打表，然后搜索，遇到可以整除的数字就除以它，然后继续搜索，直到它可以等于1，说明可以除尽，就说明可以表示。  
为什么 i 是44呢，因为到第45个就超出了题目数据范围，可以打表自己试试  
bool类型，dfs小知识

## AC代码 ##

#include<iostream>  
    #include<algorithm>  
    using namespace std;
    long long f[5000];
    bool dfs(int x, int n) {
        if(x == 1) return true;
        for(int i = n; i > 2; i--) {
            if(x % f[i] == 0) { 
                if(dfs(x / f[i], i))
                    return true;
            }
        }
        return false;
    }
    int main () {
        int i;
        f[0] = 0;
        f[1] = 1;
        for(i = 2; i <= 44; i++) {
            f[i] = f[i-1] + f[i-2];
        }
        int t;
        cin >> t;
        while(t--) {
            long long x;
            scanf("%lld", &x);
            if(x == 0)
                printf("Yes\n");
            else if(dfs(x, i-1))
                printf("Yes\n");
            else 
                printf("No\n");
        } 
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5167]: http://acm.hdu.edu.cn/showproblem.php?pid=5167
[20150810201453839]: /images/20220612/69e3c3941bdf4195b38c9f6af4a79096.png