专栏首页HansBug's Lab3713: [PA2014]Iloczyn

3713: [PA2014]Iloczyn

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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 1475: 方格取数

    1475: 方格取数 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 578  Solved: 309 [Subm...

    HansBug
  • 1627: [Usaco2007 Dec]穿越泥地

    1627: [Usaco2007 Dec]穿越泥地 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 504  So...

    HansBug
  • 3404: [Usaco2009 Open]Cow Digit Game又见数字游戏

    3404: [Usaco2009 Open]Cow Digit Game又见数字游戏 Time Limit: 3 Sec  Memory Limit: 128 ...

    HansBug
  • 1475: 方格取数

    1475: 方格取数 Time Limit: 5 Sec  Memory Limit: 64 MB Submit: 578  Solved: 309 [Subm...

    HansBug
  • 3404: [Usaco2009 Open]Cow Digit Game又见数字游戏

    3404: [Usaco2009 Open]Cow Digit Game又见数字游戏 Time Limit: 3 Sec  Memory Limit: 128 ...

    HansBug
  • ESP8266使用详解--基于Lua脚本语言ESP8266刷AT固件与nodemcu固件轻松使用8266

    这些天,,,,今天终于看到了希望,,,天道酬勤 先说实现的功能...让ESP8266连接无线网,然后让它建立服务器,,我的客户端连接上以后,发给客户端发数据模块...

    杨奉武
  • 谈谈promise/async/await的执行顺序与V8引擎的BUG

    细心的朋友肯定会发现前面第 6 步,如果async2函数是没有async关键词修饰的一个普通函数呢?

    心谭博客
  • UART

    UARTRS232 RS485 RS422区别RS232物理接口RS485物理接口RS422物理接口UART通信协议UART设计波特率产生模块发送模块接收模块顶...

    瓜大三哥
  • 值得深思的18大效应与定律

    源 / 人民网 文 / 老何

    顶级程序员
  • Android View绘制流程分析

    我们刚接触android开发的时候,应该都是从写布局开始的,在写布局的时候一般组长都要求我们少嵌套,这个是为什么呢?这个就要从我们今天要分析的invalidat...

    曾大稳

扫码关注云+社区

领取腾讯云代金券