コンテスト中はもちろん、しばらくの間は解説を読んでも理解できなかった。
フェルマーの小定理使うと解けるらしいが、Wikipediaによると、
互いに素な$2$数$a$と$p$の間には、$a^p≡a\quad(mod\quad p)$が成り立つ。
問題文より$2^{16}+1$は素数であり、
また、$a_1=1$、$a_{n+1}=2^{a_n+1}$より$a_n$は常に$2$のべき乗なので、
$2^{16}+1$と$a_{100}$は互いに素である。
まずは検討。
$a_2=2^{a_1+1}=2^{1+1}=4$
$a_3=2^{a_2+1}=2^{4+1}=32$
$a_4=2^{a_3+1}=2^{32+1}=2^{33}$
計算できないし、見るからに$2^{16}+1$より大きいので、ここから$a^p≡a$を使うはず。
$a_4=2^{33}$
$=(2^{16}+1)×2^{17}-2^{17}$
$≡-2^{17}=(2^{16}+1)×(-2)+2$
$≡2$
$a_5≡2^{2+1}$とはいかない気がするので、まだまだ解ける気がしない。
$a_5=2^{a_4+1}$なので、
$a_5=2^{2^{33}+1}$
$=(2^{16}+1)×2^{2^{33}+1-16}-2^{2^{33}+1-16}$
$≡-2^{2^{33}+1-16}$
$=(2^{16}+1)×(-2^{2^{33}+1-16×2})+2^{2^{33}+1-16×2}$
$≡2^{2^{33}+1-16×2}$
$≡2^{2^{33}+1-16×4}$ (たぶん)
:
:
$≡2^{2^{33}+1-2^{33}}$
$≡2$
！？
もしかして、延々と$2$が続く？
整理すると、
$2^{2^{16}+1}≡2\quad(mod\quad 2^{16}+1)$より$2^{2^{16}}≡1$なので、
$2^{16}×2^{16}×…≡2^{16n}≡1$も言える。
ということは、
$a_5=2^{a_4+1}$は$a_4$が$2$のべき乗であり、$2^{16}$の倍数でもあるので、
$a_5≡2^{0+1}≡2$。
$a_5$以降も同様に$2$のべき乗であり、$2^{16}$の倍数でもあるので、
$a_{100}≡2$が言え、解は$2$である。