首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >3713: [PA2014]Iloczyn

3713: [PA2014]Iloczyn

作者头像
HansBug
发布2018-04-11 10:39:02
4550
发布2018-04-11 10:39:02
举报
文章被收录于专栏:HansBug's LabHansBug's Lab

3713: [PA2014]Iloczyn

Time Limit: 1 Sec  Memory Limit: 128 MB

Submit: 327  Solved: 181

[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

Sample Output

TAK TAK NIE NIE TAK

HINT

Source

鸣谢Jcvb

题解:一开始我还想着怎么预处理,但是后来发现貌似也就\( \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.
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2015-05-01 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 3713: [PA2014]Iloczyn
  • Description
  • Input
  • Output
  • Sample Input
  • Sample Output
  • HINT
  • Source
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档