C - 153
Benihuki
3
s
1024
MB
400
点
問題文
1 2 3 4 5 6 7 8 9 から成る長さ $N$ の文字列 $S$ が与えられます。以下の $Q$ 個のクエリに与えられる順番で答えてください。
$k$ 番目のクエリは以下の形式で与えられます。
$l_k$ $r_k$
$S$ の $l_k$ 文字目から $r_k$ 文字目までを取り出した部分文字列に対し、その部分文字列を十進法で解釈したときの整数を $M$ とおきます。
$M$ に対して、次の操作を最小何回（$0$ 回でもよい）繰り返せば $153$ にできるか求めてください。
- 正の整数 $n$ に対して、$n$ を十進法で表したときの各桁の $3$ 乗の和をとる。
ただし何回操作を繰り返しても $153$ にできない場合は $-1$ と出力してください。
制約
- $1\leq N \leq 1.5 \times 10^5$
- $1 \le Q \le 1.5 \times 10^5$
- $S$ は
123456789から成る長さ $N$ の文字列 - $1 \le l_k \le r_k \le N$（$1 \le k \le Q$）
- $N, Q, l_k, r_k$ は整数
この問題には部分点が設定されている。
- $Q = 1, l_1 = 1, r_1 = N$ をみたすデータセットに正解した場合は、300点が与えられる。
入力
入力は以下の形式で標準入力から与えられる。
$N$ $Q$
$S$
$l_1$ $r_1$
$\vdots$
$l_Q$ $r_Q$
出力
与えられるクエリの順に、答えを1行ずつ合計$Q$行出力してください。
入力例 1
6 3
815324
5 6
2 4
1 6
出力例 1
3
0
-1
1番目のクエリについて、$S$ の $5$ 文字目から $6$ 文字目を取り出すと 24 となるため $M = 24$ となります。
$24$ に操作を1回行うと、$2^3 + 4^3 = 72$ となります。
同様に繰り返していくと $7^3 + 2^3 = 351$、$3^3 + 5^3 + 1^3 = 153$ となるため、$3$ 回の操作で $153$ にすることができました。
2番目のクエリについて、$M = 153$ と既に $153$ になっているため $0$ と出力します。
3番目のクエリについて、$M = 815324$ は何回操作を繰り返しても $153$ にならないことが証明できるので $-1$ と出力します。
なお、この入力は部分点の制約を満たしていません。