[常州市赛 2023] 数学作业

Luogu
IDLGB4219
Time1000ms
Memory512MB
DifficultyP3
搜索2023江苏剪枝科创活动小学活动
今天小 X 的数学老师带领大家学习了斐波那契序列: 斐波那契序列指的是这样一个数列:$\{1,2,3,5,8,13,21,34\}$。从第 $3$ 个数开始,每个数都是前两个数的和,比如 $8=3+5,34=13+21$。数列里的数叫做斐波那契数。 一个数 $n$ 的斐波那契表示是指把 $n$ 写成若干个互不相同的斐波那契数的和。一个数可以有多种不同的斐波那契表示。比如 $14$ 有三种斐波那契表示:$14=1+13,14=1+5+8,14=1+2+3+8$。数学老师给小 X 留下了一个数学作业,她告诉小 X 一个正整数 $n$,想让小 X 算出 $n$ 有多少种不同的斐波那契表示。 小 X 请你帮助他完成他的数学作业。 ## Input 第一行为一个正整数 $n$。 ## Output 输出一行一个整数表示答案。 [samples] ## Background 搬运自 <http://czoj.com.cn/p/676>。数据为民间数据。 ## Note |测试点编号|$n$| |:-:|:-:| |$1\sim5$|$1\le n\le 10^4$| |$6\sim8$|$1\le n\le 10^9$| |$9\sim10$|$1\le n\le 10^{12}$|
Samples
Input #1
14
Output #1
3
Input #2
1110
Output #2
21
Input #3
1000000000000
Output #3
283392
API Response (JSON)
{
  "problem": {
    "name": "[常州市赛 2023] 数学作业",
    "description": {
      "content": "今天小 X 的数学老师带领大家学习了斐波那契序列: 斐波那契序列指的是这样一个数列:$\\{1,2,3,5,8,13,21,34\\}$。从第 $3$ 个数开始,每个数都是前两个数的和,比如 $8=3+5,34=13+21$。数列里的数叫做斐波那契数。 一个数 $n$ 的斐波那契表示是指把 $n$ 写成若干个互不相同的斐波那契数的和。一个数可以有多种不同的斐波那契表示。比如 $14$ 有三种斐波那",
      "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": "LGB4219"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "今天小 X 的数学老师带领大家学习了斐波那契序列:\n\n斐波那契序列指的是这样一个数列:$\\{1,2,3,5,8,13,21,34\\}$。从第 $3$ 个数开始,每个数都是前两个数的和,比如 $8=3+5,34=13+21$。数列里的数叫做斐波那契数。\n\n一个数 $n$ 的斐波那契表示是指把 $n$ 写成若干个互不相同的斐波那契数的和。一个数可以有多种不同的斐波那契表示。比如 $14$ 有三种斐波那...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments