P5993题解

快斗游鹿 · 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;
}