#P10095. [ROIR 2023 Day 1] 斐波那契乘积

    ID: 1268 传统题 1000ms 256MiB 尝试: 1 已通过: 0 难度: 10 上传者: 标签>搜索数学递归2023Special Judge枚举深度优先搜索,DFS斐波那契,Fibonacci

[ROIR 2023 Day 1] 斐波那契乘积

题目背景

翻译自 ROIR 2023 D1T2

斐波那契数指斐波那契数列(f0=1,f1=1,fi=fi2+fi1f_0=1,f_1=1,f_i=f_{i-2}+f_{i-1})中出现的数。

题目描述

给定一个自然数 nn,求出将其表示为大于 11 的斐波那契数的乘积的方式数量。

输入格式

第一行一个数 tt,表示数据组数。

接下来 tt 行,每行输入一个数 nn

输出格式

对于每组测试数据,输出一个数表示答案。

5
2
7
8
40
64
1
0
2
2
3

提示

样例解释:

  • 2=22=2
  • 77 无法被表示为斐波那契乘积。
  • 8=8=2×2×28=8=2\times2\times2
  • 40=5×8=2×2×2×540=5\times8=2\times2\times2\times5
  • 64=8×8=2×2×2×8=2×2×2×2×2×264=8\times8=2\times2\times2\times8=2\times2\times2\times2\times2\times2

本题使用捆绑测试。

子任务编号 分值 2n2\le n\le
11 1515 100100
22 1717 10510^5
33 99 nn22 的整数次幂
44 3838 10910^9
55 2121 101810^{18}

对于所有数据,1t501\le t\le502n10182\le n\le10^{18}