自动搬运

查看原文

来自洛谷，原作者为

	快斗游鹿 /bx

搬运于2025-08-24 22:16:18，当前版本为作者最后更新于2022-05-04 16:14:28，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

共 $T$ 组数据，对于每组数据，判断 $n$ 是否为两个斐波那契数的乘积。

思路

观察数据 $n_i\le10^9$，设 $n_i$ 能由 $x_1$，$x_2$ 两个斐波那契数相乘得到，则 $x1,x2\le10^9$。而经实测，斐波那契数第 $50$ 位为 $12586269025$，所以只需要先预处理出前 $50$ 位的斐波那契数，再一次枚举每种情况即可得出答案。总时间复杂度大概是 $O(T\times50^2)$。

代码

#include<bits/stdc++.h>
using namespace std;
long long T;
long long feb[100];
int main(){
	scanf("%lld",&T);
	feb[1]=1;
	for(long long i=2;i<=50;i++){//预处理出前50位
		feb[i]=feb[i-1]+feb[i-2];
	}
	for(long long kkk=1;kkk<=T;kkk++){//输入T组数据
		long long n;scanf("%lld",&n);bool flag=0;
		for(long long i=0;i<=50;i++){//枚举每种情况
			for(int j=0;j<=50;j++){
				if(feb[i]*feb[j]==n){
					cout<<"TAK"<<endl;
					flag=1; 
					break;
				}
			}
			if(flag==1)break;
		}
		if(!flag){
			cout<<"NIE"<<endl;
		}
	}
	return 0;
}