Let's define function $f(x,d)$ to be the number of divisors of $x$ that are not divisible by $d$ , and $d$ is prime number. What is the fastest way to count those divisors for given $x$ and $d$.
For example: Let's say $x = 6, d = 3, f(6, 3) = 2$, divisors of $x$ are $\{1, 2, 3, 6\}$, but we are not counting $3, 6$ because they are divisible by $d$.
I got the idea that in $\sqrt{x}$ steps we can loop all the divisors of $x$ and check if they are divisible by $d$. But I was thinking that this could be done faster. Can you give me some hints where to start?
Let $x=d^lk$ where $\gcd(d,k)=1$.
Then consider prime factorization of $k=\prod_{i=1}^m p_i^{n_i}$.
then the mumber of such divisors would be equal to $\prod_{i=1}^m(n_i+1)$