ACPC10B - Sum the Square

题意翻译

## 【问题描述】 当你把一个正整数的各个数位平方之后相加,你会发现一些奇妙的现象,它出现了循环。比如说{5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, 89, …}。当然,说这个性质纯粹是为了好玩。为了多一些乐趣,这里给出两张图,这是两组平凡的数列: ![](https://cdn.luogu.com.cn/upload/image_hosting/39dj68x2.png?x-oss-process=image/resize,m_lfit,h_1700,w_2250) 现在,给定两个整数$a_1$和$b_2$,分别按照上述的方式构造数列{$a_1, a_2, …, a_m$}和{${b_1, b_2, …, b_n}$},其中$a_m$ 等于 $b_n$,你的目标是使得$n+m$最小。 ### 【输入格式】 输入包含若干组数据,每组数据包含一行两个整数,分别为$a_1$和$b_1 (1 \le a_1,b_1\le10^9)$。 输入$0 \space 0$表示结束。 ### 【输出格式】 每组数据输出一行,包含:$a_1$,空格,$b_1$,空格,$n+m$。

题目描述

Take any positive number, find the sum of the squares of its digits, repeat! You’ll end up with an infinite sequence with an interesting property that we would like to investigate further. Starting with the number 5, the sequence is: (5, 25, 29, 85, 89, 145, 42, 20, 4, 16, 37, 58, . . .) The interesting part is in what comes after 58: 5 $ ^{2} $ + 8 $ ^{2} $ = 89 which is a number that’s already been seen in the sequence. In other words, after 58, the sequence will fall into the repeating cycle: 89, 145, 42, 20, 4, 16, 37, 58. What’s amazing is that this cycle will appear for many other numbers: 3, 18, 36, and 64 just to name a few. (see figure on the following page.) For some numbers, the sequence will fall into another repeating cycle by reaching 1. (see second figure on the following page) For example, starting with 19, you’ll end up with the sequence: (19, 82, 68, 100, 1, . . .) And that’s about it. Any number you choose will end up falling into a repeating cycle: Either the 89, 145, . . . cycle or the 1, . . . cycle. Given two numbers, your objective is to generate as few numbers in their sequences for the two sequences to intersect at one common number. For example, given 61 and 29, we can achieve what’s required by generating the sequences: (61, 37, 58, 89) and (29, 85, 89). Similarly, for 19 and 100, the sequences would be (19, 82, 68, 100) and (100).

输入输出格式

输入格式


Your program will be tested on one or more test cases. Each test case is specified on a single line having two integers (0 < A, B < 10 $ ^{9} $ ). The last case is followed by a dummy line made of two zeros.

输出格式


For each test case, print the following line: A B S Where A, B are as in the input and S is the (minimum) sum of the lengths of the two sequences. If the sequences starting at A and B do not intersect, then S = 0.

输入输出样例

输入样例 #1

89 89
19 100
61 19
0 0

输出样例 #1

89 89 2
19 100 5
61 19 0

说明

![](https://cdn.luogu.com.cn/upload/image_hosting/e18pbm05.png) ![](https://cdn.luogu.com.cn/upload/image_hosting/kx6804cv.png)