#P2158. 展厅(hall)

    ID: 1547 传统题 文件IO:hall 1000ms 256MiB 尝试: 41 已通过: 17 难度: 普及− 上传者: 标签>哈希表数学合肥市蜀山区区赛2026

展厅(hall)

本题需要文件读写

文件 IO 为:输入文件 hall.in,输出文件 hall.out。请使用上述文件名读入和输出。

题目描述

有 nn 个展厅,按顺序编号为 1∼n1 \sim n。为了规划参观路线,设计了如下规则:

如果当前参观的展厅编号为 xx,那么下一个参观的展厅编号计算方式如下:先求出 xx 的各位数字之和,将其平方后对展厅总数 nn 取余。若余数为 00,则下一个参观的是 nn 号展厅;否则,下一个参观的展厅编号就是该余数。

例如,当 n=100n=100,从 3838 号展厅出发:3+8=113+8=11,112=12111^2=121,121 mod 100=21121 \bmod 100 = 21,故下一个对应 2121 号展厅。

现在想知道:从起始的 xx 号展厅出发,第一次到达 11 号展厅时,总共参观了多少个展厅(包括起点的 xx 号展厅和最终到达的 11 号展厅)。如果永远无法到达 11 号展厅,请输出 -1。特别地,如果起点就是 11 号展厅,则算作 11 次参观。

输入格式

输入仅包含一行,两个正整数 nn 和 xx —— 分别表示展厅的总数和起始展厅的编号,中间用一个空格隔开。

输出格式

输出一行,一个整数。若能到达 11 号展厅,输出总参观次数;如果永远无法到达,则输出 -1。

样例输入 1

8 1

样例输出 1

1

样例输入 2

8 2

样例输出 2

-1

样例输入 3

8 3

样例输出 3

2

样例输入 4

100 38

样例输出 4

-1

样例输入 5

15 13

样例输出 5

2

说明

样例解释

  • 样例 11 解释: 从 11 号展厅出发,已经在 11 号展厅,算 11 次参观。
  • 样例 22 解释: 起点 22(第 11 次参观); 22 的数位和为 22,22=42^2=4,4 mod 8=44 \bmod 8 = 4,下一个是 44 号(第 22 次); 44 的数位和为 44,42=164^2=16,16 mod 8=016 \bmod 8 = 0,对应 88 号(第 33 次); 88 的数位和为 88,82=648^2=64,64 mod 8=064 \bmod 8 = 0,对应 88 号(第 44 次); 之后一直在 88 号展厅循环,永远无法回到 11 号,因此输出 -1。
  • 样例 33 解释: 起点 33(第 11 次参观); 33 的数位和为 33,32=93^2=9,9 mod 8=19 \bmod 8 = 1,下一个是 11 号(第 22 次)。共 22 次。
  • 样例 44 解释: 起点 3838(第 11 次参观); 3838 的数位和为 1111,112=12111^2=121,121 mod 100=21121 \bmod 100 = 21,下一个是 2121 号(第 22 次); 2121 的数位和为 33,32=93^2=9,下一个是 99 号(第 33 次); 99 的数位和为 99,92=819^2=81,下一个是 8181 号(第 44 次); 8181 的数位和为 99,92=819^2=81,下一个还是 8181 号,陷入循环,永远无法回到 11 号。
  • 样例 55 解释: 起点 1313(第 11 次参观); 1313 的数位和为 44,42=164^2=16,16 mod 15=116 \bmod 15 = 1,下一个是 11 号(第 22 次)。共 22 次。

数据范围

对于所有测试数据,保证 1≤n≤1051 \le n \le 10^5,1≤x≤n1 \le x \le n。 保证所有的输入数值均为整数。

各测试点的附加限制如下表所示:

测试点编号 n≤n \le 特殊性质
1∼21 \sim 2 88 x=1x = 1
3∼43 \sim 4 无
5∼65 \sim 6 100100
7∼87 \sim 8 10001000
99 10510^5 x=nx = n
1010 无