Hello reader!
I came across this problem and I'm not sure how to approach it. Any hints would be appreciated!
Problem:
The Fibonacci sequence is defined as F(0) = 1, F(1) = 1, F(n) = F(n-1) + F(n-2). So: 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Given N, count the number of ways to write N as a product of Fibonacci numbers, where each factor is > 1. Order does not matter (2×4 and 4×2 are the same representation).
Example: Input: 4 2 7 40 64 Output: 1 0 2 3
Constraints: - T ≤ 50 test cases - N can be up to 10^18
I have no idea where to start. How do you approach this kind of problem?
Thank you!
imo you could do something like first discretize every factor of N and then define dp[i] as the number of ways to do i
you can brute force the fibonaccis, as there's less than 60 below 10^18
welll i dont think if it that simple i thought this way but didnt find something with proof could you briefly explain
ok so first
you take every factor and discretize them (if you don't know what discretize it, it means assigning number), at most sqrt(N) * 2 because of that one thing i forgot
next you can use dp, where dp[i] = number of ways to do i and you change by going dp[x*i] += dp[i] (assuming x is fibonacci)
and becuase fibs are exponentical this should take a short time
I could make code if you want
edit: i'm stupid
well sqrt(N) * 2 in worst case equals 2e9 so not possible
according to the orange guy there is at most cbrt(N) so it's fine
I don't know how you could calulate that
edit: FUN FACT, there are 116 primes numbers in the total facrotization of the fib numbers, so you could do that
how do you get prime factorization of some specific fib number or how do you get those 116 primes??
https://r-knott.surrey.ac.uk/fibonacci/fibtable.html
look at this lil website
yeah ok fine. you win
we only need 42 fibonacci numbers, as we only care about fibonacci numbers <= 1e9(edit: this is incorrect, we need all fib numbers upto 1e18). We can do probably do a memoized dp because we only care about many states. We can keep dividing N by each fibonacci number as many times as we can.
We know that the number of divisors of $$$N$$$ is $$$\mathcal{O}(N^\frac13)$$$.
So, you can define $$$dp_i$$$ to be the number of ways to form $$$i$$$ as a product of fibonacci numbers. Note that the number of states is $$$\approx 10^6$$$. The base case will be $$$dp_1 = 1$$$ and the transitions will be $$$dp_i = \sum_{F_j \mid i} dp_{i / F_j}$$$. The answer will be stored in $$$dp_N$$$.
The complexity will depend on your implementation but assuming you will not use a map the complexity will be $$$\mathcal{O}(N^\frac13 \cdot M)$$$ where $$$M$$$ is the count of fibonacci numbers $$$\leq 10^{18}$$$, which is bounded by $$$90$$$ I think.
it's bounded by like 90
Yeah you are right.
base case should be dp1 = 1
Nice catch. Thank you.
could you provide an implementation without map??
How do you find the said $$$O(N^{\frac{1}{3}})$$$ divisors in a time faster than $$$O(N^{\frac{1}{2}})$$$ ?
You can use miller rabin
Let ans be an answer to your problem. Start by building the Fibonacci sequence up till the value is lower than N. At the same time check whether N can be divided by F(x). If you can divide it then add 1 to ans. The final answer is ans/2 because order of factors doesn't matter.
Also start from 2 as you can't use 1 as a factor.
The time complexity is maximum O(90) as there are only 90 Fibonacci numbers that are lower than 1e18.
Every fibonacci number between $$$1$$$ and $$$10^{18}$$$ except for $$$F_{6} = 8$$$ and $$$F_{12} = 144$$$ has at least one prime factor that doesn't appear in any earlier fibonacci number.
This means that we can do the following greedy algorithm:
Iterate from the largest $$$F_{i}$$$ that is below $$$10^{18}$$$ to the smallest (except for the $$$2$$$,$$$3$$$,$$$8$$$,$$$144$$$), then divide it by the highest power of $$$F_{i}$$$ possible.
If the result after the greedy algorithm isnt in the form of $$$2^{p}3^{q}$$$, then the answer is $$$0$$$.
Otherwise the result can be calculated $$$O(log n)$$$ using some janky math.