{"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/school/archive/2022-2023/ru-olymp-regional-2023-day1.pdf)。\n\n斐波那契数指斐波那契数列（$f_0=1,f_1=1,f_i=f_{i-2}+f_{i-1}$）中出现的数。\n\n## Note\n\n样例解释：\n- $2=2$。\n- $7$ 无法被表示为斐波那契乘积。\n- $8=8=2\\times2\\times2$。\n- $40=5\\times8=2\\times2\\times2\\times5$。\n- $64=8\\times8=2\\times2\\times2\\times8=2\\times2\\times2\\times2\\times2\\times2$。\n\n本题使用捆绑测试。\n\n| 子任务编号 | 分值 | $2\\le n\\le$ |\n| :----------: | :----------: | :----------: |\n| $1$ | $15$ | $100$ |\n| $2$ | $17$ | $10^5$ |\n| $3$ | $9$ | $n$ 是 $2$ 的整数次幂 |\n| $4$ | $38$ | $10^9$ |\n| $5$ | $21$ | $10^{18}$ |\n\n对于所有数据，$1\\le t\\le50$，$2\\le n\\le10^{18}$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10095","tags":["搜索","数学","递归","2023","Special Judge","枚举","深度优先搜索 DFS","Fibonacci 数列","ROIR（俄罗斯）"],"sample_group":[["5\n2\n7\n8\n40\n64","1\n0\n2\n2\n3"]],"created_at":"2026-03-03 11:09:25"}}