2
$\begingroup$

Below is what I need to calculate efficiently.

  1. Find the number of natural numbers which is divisor of both $N$ and $K$.
  2. Find the number of natural numbers which is divisor of $N$ and is divisible by $K$.
  3. Find the number of natural numbers which is divisor of N and is not divisible by K.

$$1\leq N\leq 10^{12} \\ 1\leq K \leq 10^{12}$$

$N$ would be constant for all the above queries whereas $K$ would change in the question. I know for first one I can calculate the GCD of $N$ and $K$ and then divide it by smaller of $N$ and $K$. But I have no clue about other 2 queries. please help me crack this.

1 Answers 1

1

For 1, you need the number of factors of the GCD. You can't divide this GCD by either N or K (unless N=K).

For 2, you need the number of factors of $\frac NK$

For 3, take the number of factors of N, and subtract the result from 2.

  • 0
    @ross.. thanks a lot.. one question.. i think for n=10^12 no of divisors would be very less right.. 10^12 has 169 only.. so if i am doing it directly by computing all divisors , will be it a problem on exceution time..2012-09-05
  • 0
    @Algorithmist: You'll need to factor it. You could see http://stackoverflow.com/questions/110344/algorithm-to-calculate-the-number-of-divisors-of-a-given-number2012-09-05
  • 0
    @Algorithmist: To factor numbers up to $10^{12}$ you only need primes up to $10^6$, which are quick to sieve (or read in from a data file).2012-09-06
  • 0
    regarding the second query Find the number of natural numbers which is divisor of N and is divisible by K.Finding the divisors of N/K would not yield the correct result... for e.g suppose N=154 and k=24 then divisors of N/K=>6 would be 4 ..But actually there is no divisor of N which is divisible by K..Please suggest something.2012-09-06
  • 0
    @Algorithmist: the divide is not integer division, it is real division. $\frac {154}{24}$ is not an integer, so as you say there are none. $\frac{144}{24}=6$ and there are $4$ of them, $24, 48, 72, 144$2012-09-06