首先，由p是素数，n!/(n-k)!/k!能否整除是由三个阶乘含有p因子的个数决定的。
显然n!含p因子的个数是n/p+n/p^2+n/p^3+...理由就是统计含p的个数+含两个p的个数（这样就把第二个p算进来了）+含有三个p的数的个数+...
注意上文和下文的除法都是向下取整的。
然后注意到一个不等式：
            n/p^i >= (n-k)/p^i+k/p^i。
显然成立，理由不等式的左边没有浪费，而右边把n分开以后就可能导致浪费一个p^i（例如(1+1)/2=1而1/2+1/2=0，注意向下取整）。
所以n!的p因子个数一定比(n-k)!和k!要多。（否则组合数也除不尽了）
题目中要求不能被p整除的数的个数，其实就是上面那个不等式对所有的i取等号的k的个数。下面先考虑不等式成立的条件。
注意向下取整的含义，其实就是把余数给舍去了。所以n在分为n-k和k的时候，只要n-k和k去除的余数之和等于n的余数，则不等式的等号成立。即假如n=s*p^i+t,则k取s'*n^i+t'时等号成立。直观来说，就是[0,t]这个区间不停的横移p^i，在不超过n的情况下等号成立（其实超过n也成立，不过n-k就是负数了，不在本题的考虑范围），这样的区间有s+1个。
然后考虑i-1的情况，注意需要所有的不等式都要成立，所以只要在区间[0,t]之内考虑即可，同理，t对p^(i-1)做除法取余数t'和商数s'，则满足i-1的情况的区间有s'+1个，每个区间等价于[0,t']。
这样i从最大（使p^i<=n的最大i，再大没有意义了，不需要考虑）开始一直考虑到0，对第i个不等式考虑的区间为[0,ti]，然后不断在区间内划分子区间，一直到最后n/p=(n-k)/p+k/p的区间的个数和长度都乘一起，就是所求的答案。
再返回去一看，实质上就是对n取p进制，因为所有的运算都是除p^i取商数和余数，再对余数继续对p^i-1取商数和余数，所以也可以反过来算，对p取余数和商数，再把商数对p取余数和商数。呃，总之到这里就很简单啦