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.

  • Can you also provide the url to the original question? – Apass.Jack Dec 7 at 8:55
up vote 4 down vote accepted

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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.