Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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.