# 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$
 @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.. – Algorithmist Sep 5 '12 at 18:13 @Algorithmist: You'll need to factor it. You could see stackoverflow.com/questions/110344/… – Ross Millikan Sep 5 '12 at 18:32 @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 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. – Algorithmist Sep 6 '12 at 6:11 @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