Divisible Binomial Coefficient

2 secs 1024 MB
YSatUT's icon YSatUT

nC1, nC2,  _n{\rm C}_1,\ _n{\rm C}_2,\ \cdotsと順番に調べると、計算量がO(n)O(n)になってしまうので、工夫が必要である。\\ _n{\rm C}_r=\frac{n}{1}\times\frac{n-1}{2}\times\cdots\times\frac{n+1-r}{r}=\frac{n+1-r}{r}\,_n{\rm C}_{r-1} よって、(r(rppで割れる回数)<(n+1r)<(n+1-rppで割れる回数))となるような最小のrrを求めれば良い。\\ k=(rk=(rppで割れる回数))とおくと、r=apk(ar=a\cdot p^k(appと互いに素な自然数))とおける。この時、n+1r=n+1apkn+1-r=n+1-a\cdot p^kとなり、これがpk+1p^{k+1}の倍数になれば良い。\\ ここで、l=(n+1l=(n+1ppで割れる回数))とすると、n+1=bpl(bn+1=b\cdot p^l(bppと互いに素な自然数))とおける。この時、n+1r=bplapk=pk(bplka)n+1-r=b\cdot p^l-a\cdot p^k=p^k(b\cdot p^{l-k}-a)となる。よって、bplkab\cdot p^{l-k}-appの倍数となれば良い。\\ (i)l<k{\rm (i)}l<kの時、plkp^{l-k}は整数でなく、bbppの倍数でないので、bplkab\cdot p^{l-k}-aは整数でない。よって不適。\\ (ii)l=k{\rm (ii)} l=kの時、plk=1p^{l-k}=1よりbab-appの倍数であれば良い。よって、bbppで割った余りをmmとすると、rrの最小値はmplm\cdot p^l\\ ただし、m=bm=bすなわちb<pb<pの時は、k=lk=lよりr=n+1=mplr=n+1=m\cdot p^lとなってしまい、rnr\leq nに反するので不適。\\ (iii)l>k{\rm (iii)} l>kの時、l,kl,kは共に整数よりlk1l-k\geq 1なので、plkp^{l-k}ppの倍数。よって、aappの倍数でないから、bplkab\cdot p^{l-k}-appの倍数でない。よって不適。\\ 以上の(i){\rm (i)}から(iii){\rm (iii)}より求めるmmは、n+1=bpl(bn+1=b\cdot p^l(bppと互いに素な自然数))と表した時、bbppで割った余りをmmとすると、\\ {b>pの時、mplb<pの時、なし\left\{\begin{array}{l} b>pの時、m\cdot p^l\\ b<pの時、なし \end{array}\right. この解法により、O(logpn)O({\rm log}_p{n})で解くことができる。

(参考)本文は、東京大学2015年度学部入試の理系数学第5問を一般化したものである。

質問・誤りがある場合

Twitterに連絡ください。ID : @YS55749378