Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.