nC1, nC2, ⋯と順番に調べると、計算量が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がpで割れる回数)<(n+1−rがpで割れる回数)となるような最小のrを求めれば良い。
k=(rがpで割れる回数)とおくと、r=a⋅pk(aはpと互いに素な自然数)とおける。この時、n+1−r=n+1−a⋅pkとなり、これがpk+1の倍数になれば良い。
ここで、l=(n+1がpで割れる回数)とすると、n+1=b⋅pl(bはpと互いに素な自然数)とおける。この時、n+1−r=b⋅pl−a⋅pk=pk(b⋅pl−k−a)となる。よって、b⋅pl−k−aがpの倍数となれば良い。
(i)l<kの時、pl−kは整数でなく、bはpの倍数でないので、b⋅pl−k−aは整数でない。よって不適。
(ii)l=kの時、pl−k=1よりb−aがpの倍数であれば良い。よって、bをpで割った余りをmとすると、rの最小値はm⋅pl
ただし、m=bすなわちb<pの時は、k=lよりr=n+1=m⋅plとなってしまい、r≤nに反するので不適。
(iii)l>kの時、l,kは共に整数よりl−k≥1なので、pl−kはpの倍数。よって、aはpの倍数でないから、b⋅pl−k−aもpの倍数でない。よって不適。
以上の(i)から(iii)より求めるmは、n+1=b⋅pl(bはpと互いに素な自然数)と表した時、bをpで割った余りをmとすると、
{b>pの時、m⋅plb<pの時、なし この解法により、O(logpn)で解くことができる。
(参考)本文は、東京大学2015年度学部入試の理系数学第5問を一般化したものである。
質問・誤りがある場合
Twitterに連絡ください。ID : @YS55749378