2269B.md (2741B)
1 Source: https://codeforces.com/problemset/problem/2269/B 2 3 B. KiaKio and Squared Numbers 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Kia and Kio spent the summer at the port of Mehragan, where $n$ lighthouses stand on the cliffs facing the dark sea. 22 23 The lighthouses of Mehragan do not give light. Every night a number is written in fire on each of them, and the sailors read their way from those numbers. 24 25 The law of the lighthouses is this: if a lighthouse shows $x$ tonight, then tomorrow night it shows the sum of the squares of the decimal digits of $x$. 26 27 For example, a lighthouse showing $23$ will show $2^2+3^2=13$ tomorrow, then $1^2+3^2=10$, and then $1$. 28 29 On night $0$ of the season, lighthouse $i$ shows the number $a_i$. From that night on, the law is applied once every night, forever. 30 31 Kio calls two lighthouses $i$ and $j$ in tune if there exists a night after which, forever, both of them show exactly the same number on every single night. 32 33 Kia asks: how many pairs $(i, j)$ with $i \lt j$ are in tune? 34 35 Input 36 37 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows. 38 39 Each test case consists of two lines. 40 41 The first line of each test case contains a single integer $n$ ($1 \le n \le 1000$) — the number of lighthouses. 42 43 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the number shown by each lighthouse on night $0$. 44 45 It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$. 46 47 Output 48 49 For each test case, print a single integer — the number of pairs $(i, j)$ with $i \lt j$ such that lighthouses $i$ and $j$ are in tune. 50 51 Example 52 53 Input 54 55 ``` 56 4 57 58 5 59 60 7 4 16 4 2 61 62 4 63 64 1 7 10 100 65 66 3 67 68 4 16 37 69 70 3 71 72 2 20 4 73 ``` 74 75 Output 76 77 ``` 78 1 79 80 6 81 82 0 83 84 1 85 ``` 86 87 Note 88 89 In the first test case: 90 91 * Lighthouse $1$ starts at $7$: $7 \to 49 \to 97 \to 130 \to 10 \to 1$, and it stays at $1$ forever. 92 * Lighthouses $2$ and $4$ both start at $4$, so they show the same number on every night. 93 * Lighthouse $3$ starts at $16$ and lighthouse $5$ starts at $2$; each of them is at a different point of the cycle Kio found, and never matches anybody. 94 95 So the only pair in tune is $(2, 4)$, and the answer is $1$. 96 97 In the second test case, every lighthouse sooner or later reaches $1$ and stays there, so all of them are pairwise in tune, which gives $6$ pairs. 98 99 In the fourth test case, on night $1$, lighthouse $2$ shows $2^2+0^2 = 4$, and lighthouse $1$ shows $2^2 = 4$. From night $1$ on, they are identical forever. Lighthouse $3$ starts at $4$, so it is one night ahead of both of them and is in tune with neither.