ARC224 A - Attach 00

00をつける

考え方

愚直に考えると、$\times 1$ から順に試し、string 化して、"00" を含むか調べたくなる。
これにどのくらい計算量がかかるか考えてみる。

どんなに遅くても、$\times 100$ （末尾 $2$ 桁が "00"）で発見される。
すなわち、各クエリ $100$ 回の調査で済む。

$k \times i$ の桁数が最大 $11$ 桁なので、"00" を含むかどうかの調査は $10$ 回の処理で済むはず。

ということで、計算量はおよそ $1000Q$ くらいである。
つまり、愚直解がそのまま通る。

$2$ つ目のテストケースのみ考える。

入力を受け取る。

k: 6801

$i=1$ から順に、$k \times i$ の十進表記に "00" が含まれるか確認する。

$i=1$ のとき、値は $6801$。
"6801" に "00" は含まれない。

$i=2$ のとき、値は $13602$。
"13602" に "00" は含まれない。

$i=3$ のとき、値は $20403$。
"20403" に "00" は含まれない。

$i=4$ のとき、値は $27204$。
"27204" に "00" は含まれない。

$i=5$ のとき、num=34005。
"34005" に "00" が含まれるので、これを答えとしてループを終了する。

以上より、答えは $34005$ である。

答えは、int 型からはみ出る。
long long 型を用いること。

特になし。