0
$\begingroup$

Quite much time ago I found task where I was pleased to compute number of divisors (they are primes!) excluding numbers from set S (in other words, set S should only contain divisors of number N, which is easy). Next I'm doing prime factorization so I receive $N = p_1^{a_1} \times p_2^{a_2} \times ... \times p_k^{a_k}.$
Next number of divisors D of number N is $(a1+1)(a2+1) ... (ak+1)$ and requires number is $D-|S|$

For example we have number N=58 and at beginning 2 elements in the set: $2,3$ 2 divides 58, but 3 doesn't so we have only in set 2. prime factorization of 58 is $2^1+29^1$ so number of divisors D is (1+1)(1+1)=4. Assume that 58 isn't divisor of 58, so we have 3 divisors. Finally, our result is$ D-|S|=2$

Today I came up with this solution, but it's too slow approach. Is there any faster? Thanks for any hints, solutions, Math Friend. Cheers Chris

P.S there is link to this task: https://www.spoj.pl/problems/HABLU/

EDIT: Having had a look at the link, I'm going to try to restate the problem in a more standard way. You are given a set $S$ of primes, and a positive integer $N$. You are to find out how many divisors $N$ has, not counting those that are multiples of one or more of the primes in $S$.

  • 0
    If $n = p_1^{a_1} \ldots p_n^{a_n}$ and $S = \{p_{i}\}_{i \in I}$ then I think the number of divisors excluding $S$ is $\prod_{i \in \{1, \ldots, n\} \setminus I} (1+a_i)$ (the product of $(1+a_i)$ excluding values $i \in I$). To compute it, divide $n$ by elements of $S$ as long as you can, then compute the number of divisors of the resulting number.2011-07-11
  • 0
    Perhaps you didn't notice the line "S only contains primes or 1".2011-07-11
  • 0
    There is ambiguity. Does $\:p\in S\:$ mean that you wish to exclude all divisors divisible by $\:p\:,\:$ or does it mean to exclude only the divisor $\:p\:$?2011-07-11
  • 0
    Sorry for lack of explaination. I want to exclude all divisors which are divisible by $p$ from $S$2011-07-11
  • 0
    My previous answer still seems applicable to me. Use your formula $(a_1+1)(a_2+1)\ldots $ including only those $a_i$ that correspond to primes not in $S$2011-10-10

1 Answers 1