Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 327 Solved: 181
斐波那契数列的定义为: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,…你的任务是判断给定的数字能否被表示成两个斐波那契数的乘积。
第一行包含一个整数t(1<=t<=10),表示询问数量。接下来t行,每行一个整数n_i(0<=n_i<=10^9)。
输出共t行,第i行为TAK(是)或NIE(否),表示n_i能否被表示成两个斐波那契数的乘积。
5 5 4 12 11 10
TAK TAK NIE NIE TAK
题解:一开始我还想着怎么预处理,但是后来发现貌似也就\( \log M \)个数字(虽然显然没这么少,但实际上也就不超过60个的样子)在\( {10}^{9} \)一下,然后\( T \leq 10 \),暴力枚举轻松水过(PS:呵呵呵逗比的我还用了个平衡树来维护,但后来才想到貌似二分查找就够了= =)
1 /**************************************************************
2 Problem: 3713
3 User: HansBug
4 Language: Pascal
5 Result: Accepted
6 Time:0 ms
7 Memory:244 kb
8 ****************************************************************/
9
10 var
11 a:array[0..1000] of int64;
12 lef,rig,fix:array[0..1000] of longint;
13 i,j,k,l,m,n,head,t:longint;
14 a1:int64;
15 procedure rt(var x:longint);
16 var f,l:longint;
17 begin
18 if (x=0) or (lef[x]=0) then exit;
19 f:=x;l:=lef[x];
20 lef[f]:=rig[l];
21 rig[l]:=f;
22 x:=l;
23 end;
24 procedure lt(var x:longint);
25 var f,r:longint;
26 begin
27 if (x=0) or (rig[x]=0) then exit;
28 f:=x;r:=rig[x];
29 rig[f]:=lef[r];
30 lef[r]:=f;
31 x:=r;
32 end;
33 procedure ins(var x:longint;y:longint);
34 begin
35 if x=0 then
36 begin
37 x:=y;
38 exit;
39 end;
40 if a[y]<=a[x] then
41 begin
42 if lef[x]=0 then lef[x]:=y else ins(lef[x],y);
43 if fix[lef[x]]<fix[x] then rt(x);
44 end
45 else
46 begin
47 if rig[x]=0 then rig[x]:=y else ins(rig[x],y);
48 if fix[rig[x]]<fix[x] then lt(x);
49 end;
50 end;
51 function check(x:longint;y:int64):boolean;
52 begin
53 if x=0 then exit(false);
54 if a[x]=y then exit(true);
55 if y<a[x] then exit(check(lef[x],y)) else exit(check(rig[x],y));
56 end;
57 begin
58 a[1]:=0;a[2]:=1;head:=0;randomize;
59 for i:=3 to 60 do a[i]:=a[i-1]+a[i-2];
60 for i:=1 to 60 do
61 begin
62 lef[i]:=0;rig[i]:=0;fix[i]:=random(maxlongint);
63 ins(head,i);
64 end;
65 readln(t);
66 while t>0 do
67 begin
68 readln(a1);
69 if a1=0 then writeln('TAK') else
70 begin
71 j:=0;
72 for i:=2 to 60 do
73 begin
74 if a[i]>a1 then break;
75 if (a1 mod a[i])<>0 then continue;
76 if check(head,a1 div a[i]) then
77 begin
78 j:=1;writeln('TAK');
79 break;
80 end;
81 end;
82 if j=0 then writeln('NIE');
83 end;
84 dec(t);
85 end;
86 readln;
87 end.