hdu 5167 Fibonacci（dfs）

2024-06-15 19:38

文章标签 dfs hdu fibonacci 5167

本文主要是介绍hdu 5167 Fibonacci（dfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Fibonacci

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1003 Accepted Submission(s): 264

Problem Description

Following is the recursive definition of Fibonacci sequence:

F i = ⎧ ⎩ ⎨ 01 F i - 1 + F i - 2 i = 0 i = 1 i > 1

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,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

Sample Output

  Yes
No
Yes

Source

BestCoder Round #28

题目就是给出Fibonacci数列给出一个整数n 问这个整数是否能够表示成数列中的数的乘积

在做BC时理解成两个数的乘积怎么做都不对

快要结束时才理解是表示成若干数的乘积

然后就写了一下还是不对后来想想当时那个做法是有问题的

当时的做法是用数列中的数依次去除如果出现一个数可以整除这个数就把这个数在该数中除尽

然后再去看下一个数是否可以整除这个数

其实在数列中遇到一个数可以整除这个数时我可以选择用它除或者不用的

所以在遇到某个特殊数据时有问题

在数列中把所有可以整除这个数的数（除了0和1）拿出来放到一个数组中存储

然后我从第一个开始进行搜索我可以选择用它或者不用进行深搜

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 10010
#define ll __int64
#define bug cout<<"here"<<endl;
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)using namespace std;const ll INF=1000000000;
ll f[2000];
ll b[2500];
int num;
int cnt;//记录该数能被多少个FAC数列中的值整除
void init()
{num=2;f[0]=0;f[1]=1;for(int i=2;;i++){f[i]=f[i-1]+f[i-2];if(f[i]>INF)break;else num++;
//        cout<<num<<"  "<<"   "<<i<<"   "<<f[i]<<endl;}
}bool dfs(ll x,int step)
{if(x==1)  return 1;for(int i=step;i<cnt;i++){if(x%b[i]==0){if(dfs(x/b[i],i))return 1;}}return 0;
}int main()
{ll n;init();int tc;scanf("%d",&tc);while(tc--){scanf("%I64d",&n);if(n==0){puts("Yes");continue;}cnt=0;for(int i=3;i<num;i++){if(n%f[i]==0){b[cnt++]=f[i];}}if(dfs(n,0))puts("Yes");else puts("No");
//        for(int i=3;i<num;i++)
//        {
//            if(n%f[i]==0)
//            {
//                while(n%f[i]==0)
//                {
//                    n/=f[i];
//                }
//            }
//        }
//        if(n==1)
//            puts("Yes");
//        else puts("No");}return 0;
}