Counting the number of multiples of number A that perfectly divides the number B

Question

What is the best way of counting the number of multiples of number A that perfectly divides the number B.

This is the sub problem for one of the questions I am solving on codechef. This is the best I could come up with.

int func(int A,int B){
    int res = 0;
    int i = 1;
    while(A * i <= B){
        if(!(B %(A * i))){
            res++;
        }
        i++;
    }
    return res;
}

However,this is timing out for some of the cases. I am told that this can solved in O(sqrt(n)). Any help would be appreciated.

Answer 1

Start by checking whether $A$ divides $B$. If it doesn't, we're done, the answer is $0$. If it does, let $C = \frac{B}{A}$. The numbers you're looking for are all of the form $AM$ where $M$ divides $C$, so all you need is the number of divisors of $C$.

Let $C=p_0^{c_0}...p_n^{c_n}$ be the prime decomposition of $C$. The number of dividers of $C$ is then $\prod\limits_{i}(c_i+1)$, so the problem boils down to the prime decomposition of $C$, which can indeed be done in $O(\sqrt{C})$:

residue = C
divider = 2
number_of_prime_dividers = 0
factors = empty array
while((residue >= divider) and (divider <= sqrt(C))
{
    if(divider divides residue)
    {
        number_of_prime_dividers = number_of_prime_dividers +1
        factors[number_of_prime_dividers] = 0
    }
    while( divider divides residue )
    {
        residue = residue / divider
        factors[number_of_prime_dividers] = factors[number_of_prime_dividers] + 1
    }
    divider = divider + 1
}
if(residue != 1)
{
    number_of_prime_dividers = number_of_prime_dividers +1
    factors[number_of_prime_dividers] = 1
}

This algorithm works because by construction, every time dividerdivides residue, then it means that divideris prime (if divider is composite then all the factors of divider are strictly smaller than divider and thus have already been removed from residue). Once we reach sqrt(C), if residue != 1 we know that residue is prime, which concludes the decomposition.