　まず $f(2n)=f(n)$ であることを示す.\
　$(1+x)^{2n}=[(1+x)^n]^2$ の両辺の $x^{2m}$ の係数を考えることで
　　$$\_{2n}\mathrm{C}\_{2m}=(\_{n}\mathrm{C}\_{m})^2+2\_{2n}\mathrm{C}\_{m+1}\cdot\_{2n}\mathrm{C}\_{m-1}+\cdots$$
すなわち $\_{2n}\mathrm{C}\_{2m}$ と $\_{n}\mathrm{C}\_{m}$ の偶奇は一致する. 同様に, 同じ式の $x^{2m+1}$ の係数を考えることで $\_{2n}\mathrm{C}\_{2m+1}$ は常に偶数であるから, 以上より $f(2n)=f(n)$ であることが示された.\
　次に $f(2n+1)=2f(n)$ であることを示す. 以下の等式に留意する.
　　$$\_{2n+1}\mathrm{C}\_{m+1}=\_{2n}\mathrm{C}\_{m}+\_{2n}\mathrm{C}\_{m+1}$$
ここで上の考察より $\_{2n}\mathrm{C}\_{m}$ と $\_{2n}\mathrm{C}\_{m+1}$ の偶奇は異なるから, $\_{2n}\mathrm{C}\_{m}$ が奇数ならば $\_{2n+1}\mathrm{C}\_{m}$ および $\_{2n+1}\mathrm{C}\_{m+1}$ はともに奇数である ($m=2n$ でも正しい). これより $f(2n+1)=2f(n)$ が示された.\
　これで準備は整ったので, 計算が可能である. $5^{16}\equiv 1\pmod{16}$ に留意すれば,
　　$$f(10^{16}-2^{16})=f(5^{16}-1)=f\left(\dfrac{5^{16}-1}{16}\right)$$
一方で, $f(2n+1)=2f(n)$ を繰り返し用いれば,
　　$$f(10^{16}+7\cdot2^{17})=f(5^{16}+14)=2f\left(\dfrac{5^{16}+13}{2}\right)=\cdots=16f\left(\dfrac{5^{16}-1}{16}\right)$$
以上より, 求める商は $\textbf{16}$ である,
公式解説
https://onlinemathcontest.com/contests/omc011/editorial/74
公式解説では二項係数の等式とパスカルの三角形での等式をもとに漸化式を構築していたが，Kummer's theoremにより，$f(n)$ が直ちに求まる．OMCでは比較的よく問われるので，知っておくとよい．  
**Kummer's theorem**  
 　$p$ を素数とする．${}\_{m}\mathrm{C}\_{n}$ が $p$ で割り切れる最大の回数は $p$ 進数の表示で $(m-n) + n$ を計算したときの繰り上がりの回数と等しい．  
**証明**  
　[こちら](https:\/\/en.wikipedia.org\/wiki\/Kummer%27s_theorem)や[こちら](https:\/\/manabitimes.jp\/math\/1330)を参照のこと．
ルジャンドルの定理によって $n!$ の $p$ で割れる回数が，（$p$ 進数表示での各桁の和の関数を定めておけば）具体的に書けるため， ${}\_{m}\mathrm{C}\_{n}$ が $p$ で割れる回数もこの表示を行うことができ，その表示と $p$ 進数表示での和計算の繰り上がりの対応付けを見るような証明となっている．

この定理を $p=2$ で用いることで，${}\_{n}\mathrm{C}\_{k}$ が奇数であることと， $n-k$ と $k$ の2進表示での和の計算で繰り上がりが発生しないことが同値であることがわかる．これは $n-k$ と $k$ の2進表示において，同じ桁に $1$ が存在しないことと同値であり，和である $n$ の2進表示で $0$ となる桁に対しては $n-k$ および $k$ の2進表示の同じ桁でも $0$ となり，$1$ となる桁に対しては $k$ の同じ桁での2進表示は $1,0$ の2通りの表示がありうる．以上の議論をまとめると，$n$ の2進表示での $1$ の個数を $\mathrm{popcount}(n)$ と書くことにすると，$f(n) = 2^{\mathrm{popcount}(n)}$ であることがわかる．

あとは公式解説とほぼ同様だが，2進表示を追うと少し速く計算できる．$5^{16} \equiv 1 \pmod {16}$ より，$5^{16}-1$ は2進表示で下4桁がすべて $0$ で，$5^{16}+14=(5^{16}-1)+ 15$ は2進表示で $5^{16}-1$ の2進表示の下4桁をすべて $1$ に変えたものと一致し，与えられた二数の $\mathrm{popcount}$ の差は $4$ になるため，求める値は $2^4 = \mathbf{16}$ となる．
Kummer's theorem
https://onlinemathcontest.com/contests/omc011/editorial/74/400
　Lucas's theoremを利用することでも $f(n)$ の値を求めることができる．  
**Lucas's theorem**  
　任意の素数 $p$ と非負整数 $m,n$ に対し，$m,n$ の $p$ 進数表示をそれぞれ $\overline{m_km_{k-1}\cdots m_0},\overline{n_kn_{k-1}\cdots n_0}$ としたとき，次が成立する．

$${}\_{m}\mathrm{C}\_{n} \equiv \prod_{i=0}^k {}\_{m_i}\mathrm{C}\_{n_i} \pmod{p}$$

**証明**  
　[こちら](https:\/\/manabitimes.jp\/math\/1324)や[こちら](https:\/\/drive.google.com\/file\/d\/1BcJTLjQaelZ4w_70oHKyImC2I8zLfyrt\/view)を参照のこと．  

この定理を $p=2$ で用いることで，${}\_{n}\mathrm{C}\_{k}$ が奇数であることと，$k$ で立っているビットの集合が $n$ で立っているビットの集合の部分集合であることと同値であることがわかる．これより，$f(n)=2^{\mathrm{popcount}(n)}$ がわかる．

あとは[bzuLさんのユーザー解説](https:\/\/onlinemathcontest.com\/contests\/omc011\/editorial\/74\/400)と同様．
Lucas's theorem
https://onlinemathcontest.com/contests/omc011/editorial/74/775
　正整数 $n$ に対して, ${}\_{n}\mathrm{C}\_{k}$ が奇数であるような整数 $0\leq k\leq n$ の個数を $f(n)$ で表します. 例えば,
$${}\_{3}\mathrm{C}\_{0} =1,\quad {}\_{3}\mathrm{C}\_{1} =3,\quad {}\_{3}\mathrm{C}\_{2} =3,\quad {}\_{3}\mathrm{C}\_{3} =1$$
なので, $f(3) =4$ です. このとき, $\displaystyle \frac{f\left( 10^{16} +7\times 2^{17}\right)}{f\left( 10^{16} -2^{16}\right)}$ を求めてください.