hdu 5167 Fibonacci 打表

时间:2020-12-31 08:58:17

Fibonacci

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Problem Description
Following is the recursive definition of Fibonacci sequence:
Fi=⎧⎩⎨01Fi−1+Fi−2i = 0i = 1i > 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
3
4
17
233
 
Sample Output
Yes
No
Yes
 
Source
题意:问一个数n,能否由斐波那契数列中的某些数乘积组成;
思路:打表,能组成的全弄出来;
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
const int N=2e5+,M=4e6+,inf=1e9+,mod=1e9+;
const ll INF=1e18+;
map<ll,int>m;
ll f[N];
priority_queue<ll,vector<ll>,greater<ll> >q;
void init()
{
int pre=;
int now=;
f[]=;
f[]=;
for(int i=;i<=;i++)
f[i]=f[i-]+f[i-];
for(int i=;i<=;i++)
if(!m[f[i]])
q.push(f[i]),m[f[i]]=;
while(!q.empty())
{
ll v=q.top();
q.pop();
for(int i=;i<=;i++)
{
if(f[i]*v<inf&&!m[f[i]*v])
{
m[f[i]*v]=;
q.push(f[i]*v);
}
}
}
}
int main()
{
init();
int T;
scanf("%d",&T);
while(T--)
{
int n;
scanf("%d",&n);
if(m[n])
printf("Yes\n");
else
printf("No\n");
}
return ;
}

hdu 5167 Fibonacci 打表的更多相关文章

  1. HDU 5167 Fibonacci 筛法&plus;乱搞

    题目链接: hdu: http://acm.hdu.edu.cn/showproblem.php?pid=5167 题意: 给你一个x,判断x能不能由斐波那契数列中的数相乘得到(一个数可以重复使用) ...

  2. hdu 5167 Fibonacci&lpar;预处理&rpar;

    Problem Description Following is the recursive definition of Fibonacci sequence: Fi=⎧⎩⎨01Fi−1+Fi−2i ...

  3. HDU 3117 Fibonacci Numbers(围绕四个租赁斐波那契,通过计&plus;&plus;乘坐高速动力矩阵)

    HDU 3117 Fibonacci Numbers(斐波那契前后四位,打表+取对+矩阵高速幂) ACM 题目地址:HDU 3117 Fibonacci Numbers 题意:  求第n个斐波那契数的 ...

  4. hdu 1496 Equations hash表

    hdu 1496 Equations hash表 题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=1496 思路: hash表,将原来\(n^{4}\)降 ...

  5. hdu 3117 Fibonacci Numbers 矩阵快速幂&plus;公式

    斐波那契数列后四位可以用快速幂取模(模10000)算出.前四位要用公式推 HDU 3117 Fibonacci Numbers(矩阵快速幂+公式) f(n)=(((1+√5)/2)^n+((1-√5) ...

  6. HDU 1021 Fibonacci Again【打表找规律】

    Fibonacci Again Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)T ...

  7. hdu 5104 素数打表水题

    http://acm.hdu.edu.cn/showproblem.php?pid=5104 找元组数量,满足p1<=p2<=p3且p1+p2+p3=n且都是素数 不用素数打表都能过,数据 ...

  8. HDU 5976 Detachment 打表找规律

    题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5976 Detachment Time Limit: 4000/2000 MS (Java/Other ...

  9. hdu Interesting Fibonacci

    Interesting Fibonacci Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Ot ...

随机推荐

  1. 为MySQL选择合适的备份方式

    数据库的备份是极其重要的事情.如果没有备份,遇到下列情况就会抓狂: UPDATE or DELETE whitout where… table was DROPPed accidentally… IN ...

  2. java的BigDecimal

    java的BigDecimal 一般设计到高精度的加法或乘法或者阶乘的求和积都会用到BigDecimal这个类. import java.util.*;import java.math.BigDeci ...

  3. js为鼠标添加右击事件

    <script language="javascript">  /*document.oncontextmenu=Youji;*/  //为当前文档添加鼠标右击事件,防 ...

  4. Cantor表 1083

    题目描述 Description 现代数学的著名证明之一是Georg Cantor证明了有理数是可枚举的.他是用下面这一张表来证明这一命题的: 1/1 1/2 1/3 1/4 1/5 - 2/1 2/ ...

  5. Windows2008 R2 X64 PHP环境搭建步骤

    Windows2008 R2 X64 PHP环境搭建步骤: 下载:Mysql5.7.23.PHP5.6.Zend.XCahe 一.安装MYSQL.导入数据: 解压MYsql压缩包,并新建Data目录, ...

  6. python 调用阿里云服务器api创建服务器

    首先安装阿里云SDK pip install aliyun-python-sdk-core pip install aliyun-python-sdk-ecs 可以配合jenkins传递参数 #!/u ...

  7. XCode iOS Simulator 模拟器

    XCode7.3下,默认带了iOS 9.3 Simulator,iOS 8.4 Simulator总是安装不成功. mac os X,里的模拟器,全屏 ,windows win键+1/2/3 切换全屏 ...

  8. maven与ide工具的整合

    maven与myeclipse的整合 1   点击window会出现 2>选择  preferences

  9. docker tar 镜像 容器相互转换

    学习 使用 docker 也有一段时间了 但是在基础去上面有些东西总是容易忘记 整理之前看到的文档,看到一个问题 怎么将一个容器导出成为tar,我本以为是首先 保存成为镜像 再 save 进行保存 查 ...

  10. FeatureTable&lpar;&rpar;

    abstract                                                            long         addFeature(Feature ...