Number of Divisor How to find the Number of divisors of a number 'n' that are also divisible by another number 'k' without looping through all the divisors of n?
I tried the following:
Stored powers of all prime factors of n in an associative array A and did similarly for k, stored the powers of all primes factors in array B.
    ans = 1
    for a in A:    // Here a is the prime factor and A[a] gives its power
        ans *= if( a is present in B ) ? 1 : A[a] + 1
    print ans

Note : It is not homework.
 A: Any divisor of $n$ that is itself divisible by $k$ can be written as $d k$, where $d$ is a divisor of $\frac nk$. Hence their number is exactly the number of divisors of $\frac nk$. 
Of course we need $k$ to be a divsor of $n$ for this to make sense at all.
A: All you have to do is compute $\sigma_0(n/k)$, where $\sigma_0(m)$ is the divisor function, which counts the number of divisors of $m$. The reason of this is that 
$$
k \, | \, m \, | \, n \quad \Longleftrightarrow \quad m = kd \quad \text{and} \quad d \, | \, n/k.
$$
This is quite easy to prove, I'll leave it up to you. Now to compute $\sigma_0(n/k)$, one can show that $\sigma$ is a multiplicative function, because $f(n) = 1$ is multiplicative, hence
$$
\sigma_0(n) = \sum_{d \, | \, n} f(d)
$$
also is (well-known theorem in number theory that $\sum_{d \, | \, n} f(d)$ is multiplicative when $f$ is). Therefore, since $\sigma_0(p^{\alpha}) = \alpha+1$, you have 
$$
\sigma_0(n) = \prod_{p \, | , n} (\alpha(n,p) + 1)
$$
where $\alpha(n,p)$ stands for the greatest power of $p$ dividing $n$. In other words, all you have to do is factor $n/k$ and use the factorization to compute $\sigma_0(n/k)$.
Hope that helps,
