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

Luogu

IDLGP10095

Time1000ms

Memory512MB

DifficultyP3

搜索数学递归2023Special Judge枚举深度优先搜索 DFSFibonacci 数列ROIR（俄罗斯）

给定一个自然数 $n$，求出将其表示为若干个大于 $1$ 的斐波那契数的乘积的方案数。 ## Input 第一行一个数 $t$，表示数据组数。接下来 $t$ 行，每行输入一个数 $n$。 ## Output 对于每组测试数据，输出一个数表示答案。 [samples] ## Background 翻译自 [ROIR 2023 D1T2](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf)。斐波那契数指斐波那契数列（$f_0=1,f_1=1,f_i=f_{i-2}+f_{i-1}$）中出现的数。 ## Note 样例解释： - $2=2$。 - $7$ 无法被表示为斐波那契乘积。 - $8=8=2\times2\times2$。 - $40=5\times8=2\times2\times2\times5$。 - $64=8\times8=2\times2\times2\times8=2\times2\times2\times2\times2\times2$。本题使用捆绑测试。 | 子任务编号 | 分值 | $2\le n\le$ | | :----------: | :----------: | :----------: | | $1$ | $15$ | $100$ | | $2$ | $17$ | $10^5$ | | $3$ | $9$ | $n$ 是 $2$ 的整数次幂 | | $4$ | $38$ | $10^9$ | | $5$ | $21$ | $10^{18}$ | 对于所有数据，$1\le t\le50$，$2\le n\le10^{18}$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[ROIR 2023] 斐波那契乘积 (Day 1)",
    "description": {
      "content": "给定一个自然数 $n$，求出将其表示为若干个大于 $1$ 的斐波那契数的乘积的方案数。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10095"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个自然数 $n$，求出将其表示为若干个大于 $1$ 的斐波那契数的乘积的方案数。\n\n## Input\n\n第一行一个数 $t$，表示数据组数。\n\n接下来 $t$ 行，每行输入一个数 $n$。\n\n## Output\n\n对于每组测试数据，输出一个数表示答案。\n\n[samples]\n\n## Background\n\n翻译自 [ROIR 2023 D1T2](https://neerc.ifmo.ru/...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments