Given a set of integers $S$, which will contain no more than $100$ integers. Now, what would be the fastest approach to find $M$ which is a product of one or more integers from $S$ (and multiple usage allowed) not exceeding another given value $X$.
Is this possible to achieve on $O(\sqrt{X})$ or lower complexity?
I have tried recursively dividing $X$ with one of the integers from $S$ and then reconstruction on the return way. But I knew that would not even be viable when $X$ get to a sizable amount. For this problem, $X$ will not be larger than a $64$ bit integer.
Also tried finding result for $\sqrt[3]{x}$ and then combining them, and I don't think that will produce a correct answer.
If the given set is composed of fibonacci numbers, there is a sequence in OEIS. Although, generating this doesn't look easy to me.
I'm no math guy however, but I think this is an interesting problem. Help appreciated.