Number of binomial coefficient's of n whose mod with p gives 0..

Binomial Coefficient formula:

nCr = n! / (r! * (n-r)!)



We can find the multiplicity of p in the binomial coefficient (nCr) 

by the regular formula i.e.,  ∑(nCr)/(p^k)

                             k=0



for example multiplicity of 2 in (100Cr) is (1+1)*(1+1)*(1+1) = 8

(since we have 1*2^2 + 1*2^5 + 1*2^6)

so coefficients not divisible by 2 are = 8 

Coefficients Divisible by 2 are = 100 + 1 - 8 = 93

( (n + 1) Since there will be n + 1 binomial coefficients)



Taking more simpler example 

multiplicity of 2 in (4Cr) is (1+1) = 2 (Since 4 = 1*2^2)

so coefficients not divisible by 2 are = 2

Coefficients Divisible by 2 are = 4 + 1 - 2 = 3



More example 

Multiplicity of 5 in (18Cr) is (3+1) * (1+1) = 8 ( Since 18 = 3*5^0 + 1*5^3)

so coefficients not divisible by 5 are = 8 

Coefficients Divisible by 5 are = 18 + 1 - 8 = 11

BigInteger Coefficients_Divisible(int no,int mod)

{

    BigInteger num=no, nondivisible = 1;

    while( num > 0 )

    {        nondiv = nondiv * ((num % mod) + 1)

        num = num / mod ;

    }

    return (no + 1 - nondivisible)

}