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
    @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