# Find total number of sets of integers which satisfy a given equality and inequality

Compute the total number of different sets of integers a1, a2,..,an which satisfy the following equality and constraints:

$$\frac{a_1.a_2.a_3..a_{\lceil\frac{n}{2}\rceil}}{a_{\lceil\frac{n}{2}\rceil+1}.a_{\lceil\frac{n}{2}\rceil+2}..a_n} = v$$

$$1 \le a_1 \le 9$$

$$0 \le a_j \le 9 \mbox{ } \forall \mbox{ } j \ge 2$$

$$0 \le v \le 10^{18}, \mbox{ } v \in I$$

$$1 \le n \le 36$$

For example: if v = 27 and n = 3, Expression would be: $$\frac{a_1.a_2}{a_3} = 27$$

and the resulting sets of possible values for a1,a2,a3 are: {3,9,1}, {6,9,2}, {9,3,1}, {9,6,2}, {9,9,3}

So the answer in this case is f(3,27) = 5.

Here the values that v can take can be every large, so the method to calculate the answer should be very efficient. I can't think of any suitable algorithm for such large values. The only thing I can think of involves prime factorization which is inefficient in terms of time. Can anybody suggest something?

Also the number of test cases to be solved can be as large as 32*104. So the method should be really fast.

-