　数列 $\\{b_n\\}$ を以下で定める． 
 $$b_1 = k,\quad b_2 = 2k^2 - 1,\quad b_{n+2} = 2kb_{n+1} - b_n$$ 

このとき， $θ = k + \sqrt{k^2-1}$ とすれば，
$$a_n = \dfrac{θ^n - θ^{-n}}{2\sqrt{k^2 - 1}},\quad b_n = \dfrac{θ^n + θ^{-n}}{2}$$ であり，特に $a_{2n} = 2a_nb_n$ 
が成り立つ．また，帰納的に
$$v_2(a_{2n+1})=0,\quad
v_2(b_n)=\begin{cases}
0 & (2\mid n)\\\\
v_2(k) & (2\nmid n)
\end{cases}$$
であることが確認できるので，$n$ が偶数のとき，
$$v_2(a_n)=v_2(n)+v_2(k)$$
である．$10^{10}$ 以下の $k$ で $v_2(k)$ が最大になるのは $k=2^{33}$ の時であるから，求める答えは $\bf{133}$ である．
公式解説
https://onlinemathcontest.com/contests/omc158/editorial/2061
　厳密性は欠けますが，以下のように推測によって解けます．

  　$a_{10^{100}}=b_1k+b_3k^3+b_5k^5+…$ となる．\
  　$a_{8}$ くらいまで漸化式に従って代入してみると，$b_1=-10^{100}$，$v_2(b_1)≦v_2(b_3),v_2(b_5),……$ が推測できる．\
  　以上の仮定を基にすると，$k=2^{33}$ のとき $f(k)$ は最大になり，答えは $\mathbf{133}$ である．\
\
  　なお，$b_1=-10^{100}$，$v_2(b_1)≦v_2(b_3)$ 部分の推測が正しいことは，次の式を帰納法で示すことで証明できましたが，$b_5$ 以降についてはよくわかっていません．\
  　$a_{2n}=2(-1)^{n-1}nk+\dfrac{4}{3}(-1)^{n}n(n+1)(n-1)k^3+……$
ユーザー解説
https://onlinemathcontest.com/contests/omc158/editorial/2061/223
　線形代数を用いて解いてみます. ここでは, $2N=10^{100}$ とします.
$a_0=0,a_1=1$ であり, 以下が成立します.
$$
\begin{pmatrix}
a_{n+2}  \\\\
a_{n+1}  \\\\
\end{pmatrix}
=
\begin{pmatrix}
2k & -1 \\\\
1 & 0 \\\\
\end{pmatrix}
\begin{pmatrix}
a_{n+1}  \\\\
a_{n}  \\\\
\end{pmatrix}
$$
　よって,
$$
\begin{aligned}
\begin{pmatrix}a_{2N+1}  \\\\
a_{2N}  \\\\
\end{pmatrix}
&=
\begin{pmatrix}
2k & -1 \\\\
1 & 0 \\\\
\end{pmatrix}^{2N}
\begin{pmatrix}
1  \\\\
0  \\\\
\end{pmatrix}\\\\
&=
\begin{pmatrix}
4k^2-1 & -2k \\\\
2k & -1 \\\\
\end{pmatrix}^{N}
\begin{pmatrix}
1  \\\\
0  \\\\
\end{pmatrix}\\\\
&=\Bigg(
2k
\begin{pmatrix}
2k & -1 \\\\
1 & 0\\\\
\end{pmatrix}-I\Bigg)^{N}
\begin{pmatrix}
1  \\\\
0  \\\\
\end{pmatrix}\\\\ 
\end{aligned}
$$
　ここで, $A=
\begin{pmatrix}
2k & -1 \\\\
1 & 0\\\\
\end{pmatrix}$ とします. 上の式を $2$ 項展開すると以下のようになります.
$$(2kA-I)^{N}=I-N\cdot 2kA+\dots+\binom{N}{m}(-2k)^mA^m+\cdots$$
　$k$ が偶数であるとき, $m\gt2$ について, $v_2(N\cdot 2k)\lt v_2\Big(\binom{N}{m}(2k)^m\Big) $ が成立します.
<details> 
<summary> 証明 <\/summary>
 $$
\begin{aligned}
&v_2\Bigg(\binom{N}{m}(2k)^m\Bigg)-v_2(N\cdot 2k)\\\\
&=v_2\Bigg(m\cdot \binom{N}{m}(2k)^m\Bigg)-v_2(m\cdot N\cdot 2k)\\\\
&=v_2\Bigg(N\cdot \binom{N-1}{m-1}(2k)^m\Bigg)-v_2(m\cdot N\cdot 2k)\\\\
&=v_2\Bigg(\binom{N-1}{m-1}\Bigg)+(m-1)v_2(2k)-v_2(m)\\\\
&\geq (m-1)v_2(2k)-v_2(m)\\\\
&\geq 2(m-1)-v_2(m)\gt 0\\\\
\end{aligned}
$$
<\/details>
　これより $M=v_2(N\cdot2k)$ としたとき以下が成立します.
$$(2kA-I)^{N}\equiv I-N\cdot 2kA\pmod{2^{M+1}}$$
$(I-N\cdot 2kA)
\begin{pmatrix}
1\\\\
0\\\\
\end{pmatrix}
=
\begin{pmatrix}
\cdots\\\\
-N\cdot 2k\\\\
\end{pmatrix}$
より, $v_2(a_{2N})=M=100+v_2(k)$ であり, $k$ が偶数であるとき $k=2^{33}$ にて, 最大値 $\mathbf{133}$ を取る.
線形代数を用いる解法(kが偶数のときのみ)
https://onlinemathcontest.com/contests/omc158/editorial/2061/618
　正整数 $k$ に対して，以下で数列 $\\{a_n\\}$ を定めたとき，$a_{10^{100}}$ が $2$ で割り切れる最大の回数を $f(k)$ とします：
 $$a_1 = 1,\quad a_2 = 2k,\quad a_{n+2} = 2ka_{n+1} - a_n.$$
$k \leq 10^{10}$ の範囲で，$f(k)$ のとりうる最大値を解答してください．