# yukicoder No.2271

問題のタイトルから想像した問題と全然違っていた。
$\sqrt{2} = 1.41421356 \cdots$ と近似する問題だと思った。
問題文も解説も何を言ってるのか分からんかった。
問題文だけなんとか解読して

$r^{2} \equiv N \pmod{5^E}$ となる $r$ を求めよ

という問題らしいということが分かった。

Cipolla みたいな難しいアルゴリズムを使いたくなるが不要。
$x$ が
$x^{2} \equiv N \pmod{5^e}$
を満たすなら、
$y^{2} \equiv N \pmod{5^{e+1}}$
であるような $y$ は、五進にしたときの最上位のみを除いた数が $x$ に一致する。
よって、桁を増やしながら探索すればいい。

解説ではこの手法を "桁DP" と呼んでいるようだが、
別段 DP をしているわけでもないので、桁DP とは普通は言わないだろう。