問題一覧 > 通常問題

No.1252 数字根D

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 132
作問者 : KazunKazun / テスター : maspymaspy
4 ProblemId : 4692 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-10-09 20:06:06

注意

この問題において, 特に明示していない場合, 数字の表記は全て十進表記とし, 入力も十進表記とする. また, 出力も各テストケースの $d$ の値に関係なく十進表記で出力せよ.

問題文

非負整数 $N$ の $d$ 進数字和 $f(N)$ を, $\displaystyle N=\sum_{j=0}^M a_j d^j$ を満たすような非負整数 $M$ と $M+1$ 個の $0$ 以上 $d-1$ 以下の整数 $a_0,\dots,a_M$ を用いて, $\displaystyle f(N)=\sum_{j=0}^M a_j$ と定義する.

次に, 非負整数 $m,N$ に対して, $f^m(N)$ を以下のように定義する: $\quad f^m(N)=\begin{cases} f(f^{m-1}(N)) & (m \geq 1) \\ N & (m=0) \end{cases}$

また, 非負整数 $N$ の $d$ 進数字根 $N^*$ を $\displaystyle N^*=\lim_{m \to \infty} f^m(N)$ と定義する. では, 非負整数 $A,B~(A \leq B)$ に対して, $\displaystyle \sum_{k=A}^B k^*$ を求めよ.

なお, 数字根は全ての非負整数に対して一意に定まることが示される.

$T$ 個のテストケースについて答えよ.

例

$N=20201009$ の $10$ 進数字根を求める.
  • $f^0(N)=N=20201009$
  • $f^1(N)=f(f^0(N))=f(N)=2+0+2+0+1+0+0+9=14$
  • $f^2(N)=f(f^1(N))=f(f(N))=f(14)=1+4=5$
  • $f^3(N)=f(f^2(N))=f(5)=5$
  • $\vdots$
となり, $N^*=5$ であることがわかる.

制約

  • $1 \leq T \leq 2000$
  • $2 \leq d \leq 10^9$
  • $0 \leq A \leq B \leq 10^9$
  • $T,d,A,B$ は全て整数である.

入力

入力は以下の形式で標準入力から与えられる. 1行目は以下の通りである. 
$T$
そして, 続く $T$ 行が $T$ 個のテストケースを表す. それぞれは以下の形式の行である. 
$d~A~B$

出力

各テストケースの出力後に改行すること.

サンプル

サンプル1
入力
3
10 99 101
9 9 18
16 12345 67890
出力
12
39
444375

[第1テストケースについて]
$99^*=9,100^*=1,101^*=2$ なので, $9+1+2=12$ である.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。