# Fastest Way To Compute below

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.

-

For 2, you need the number of factors of $\frac NK$
@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). – Ross Millikan Sep 6 '12 at 4:08
@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$ – Ross Millikan Sep 6 '12 at 13:00