You do not need to compute the binomial coefficient (n,r)
.
Count how often p
is in n!
, r!
and (n-r)!
and check if n!
has more factors p
than the other two togeter.
// sry... no python...
long count_p_in_fac(long n, long p)
{
long count = 0;
long i = 1;
long temp;
while(true)
{
temp = floor(n/pow(p,i));
count += temp;
if(temp == 0)
break;
}
return count;
}
p = input()
cnt = 0
for i in range(0,n+1):
if(count_p_in_fac(n,p) > count_p_in_fac(i,p) + count_p_in_fac(n-i,p)):
cnt += 1
print cnt
This avoids big numbers and reduces the operations.
This checks (n,r) = 0 mod p
in O(log(n))
without computing factorials. But counting a row takes O(n log n)
.
You can also speed this up by using the symmetry of (n,r)
. Computing only the first half and multiply it by two. If n
is even, you have to count the first half exept the middle r = n/2
and check add the middle after multiply by two.
And you can precompute count_p_in_fac(i,p)
for all i
.