rockdu
3713: [PA2014]Iloczyn
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 697 Solved: 381
[Submit][Status][Discuss]
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能否被表示成两个斐波那契数的乘积。
Sample Input
5
5
4
12
11
10
5
4
12
11
10
Sample Output
TAK
TAK
NIE
NIE
TAK
TAK
NIE
NIE
TAK
我是，水题之王！！！
结果这种水题我都交了5次，我可能要去死一死。简单的暴力求出斐波那契双重循环。
重要的事情说三遍 注意读题 注意读题 注意读题
另外，int 会原地起飞
#include<cstdio>
using namespace std;
long long fib[50]={},n;
int cnt=0,t;
bool judge(long long n){
if(n==0) return 1;
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
if(fib[i]*fib[j]==n)
return 1;
return 0;
}
int main(){
fib[1]=0;fib[2]=1;cnt+=2;
for(int i=3;fib[i-1]+fib[i-2]<=1e9;i++)
fib[i]=fib[i-1]+fib[i-2],cnt++;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%s\n",judge(n)?"TAK":"NIE");
}
return 0;
}
没有帐号? 立即注册