trang chủ / đề bài / icpc23_mb_a

Tích Fibonacci

Đề bài

Mô tả

Dãy Fibonacci được định nghĩa như sau: F0=1, F1=1, Fn=Fn−2+Fn−1. Một số số hạng đầu tiên của dãy Fibonacci: 1,1,2,3,5,8,13,21,34,…

Cho một số tự nhiên n, hãy đếm số cách biểu diễn n thành tích của các số Fibonacci (các số trong biểu diễn phải lớn hơn 1). Hai cách biểu diễn chỉ khác nhau về thứ tự các thừa số được coi là một.

Dữ liệu vào

Dòng đầu tiên chứa số bộ dữ liệu t (1≤t≤50). Mỗi dòng trong t dòng tiếp theo chứa một số nguyên n (2≤n≤1018).

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số cách phân tích n thành tích các số Fibonacci.

Ràng buộc

  • 1≤t≤50
  • 2≤n≤1018

Ví dụ

Input Output Giải thích
5
2
7
8
40
64
1
0
2
2
3
Số 2 có một cách biểu diễn duy nhất: 2=2. Số 7 không thể biểu diễn thành tích các số Fibonacci. Số 8 có hai cách: 8=2×2×2 và 8=8. Số 40 có hai cách: 40=2×2×2×5 và 40=5×8. Số 64 có ba cách: 26, 2×2×2×8 và 8×8.
5
6
720
1000000
13
4181
1
3
3
1
1
720=144×5=8×5×3×3×2=5×3×3×24. 1000000=8×8×56=8×56×23=56×26. 4181 là một số Fibonacci.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0