首页 > 代码库 > BZOJ 3713: [PA2014]Iloczyn
BZOJ 3713: [PA2014]Iloczyn
Description
斐波那契数列的定义为：k=0或1时，F[k]=k；k>1时，F[k]=F[k-1]+F[k-2]。数列的开头几项为0,1,1,2,3,5,8,13,21,34,55,…你的任务是判断给定的数字能否被表示成两个斐波那契数的乘积。
Input
第一行包含一个整数t(1<=t<=10)，表示询问数量。接下来t行，每行一个整数n_i(0<=n_i<=10^9)。
Output
输出共t行，第i行为TAK（是）或NIE（否），表示n_i能否被表示成两个斐波那契数的乘积。
题解:
鉴于F[44]> 1e9。于是可以把两两乘积算出来，枚举即可。
代码：
#include<cstdio>#include<cstring>#include<algorithm>#include<set>//by zrt//problem:using namespace std;int f[46];set<int> s;int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif f[0]=0;f[1]=1; for(int i=2;i<=45;i++){ f[i]=f[i-1]+f[i-2]; } int MAX=1e9; for(int i=0;i<=45;i++) s.insert(f[i]); for(int i=3;i<=45;i++){ for(int j=i;j<=45;j++){ if(f[i]*1LL*f[j]<=MAX){ s.insert(f[i]*f[j]); } } } int t,x; scanf("%d",&t); while(t--){ scanf("%d",&x); if(s.count(x)){ puts("TAK"); }else{ puts("NIE"); } } return 0;}
BZOJ 3713: [PA2014]Iloczyn
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。