problem c
alice got a hold of an old calculator that can display n digits. she was bored enough to come up with the following time waster.
she enters a number k then repeatedly squares it until the result overflows. when the result overflows, only
the n most significant digits are displayed on the screen and an error flag appears. alice can clear the error and continue squaring the displayed number. she got bored by this soon enough, but
wondered:
“given n and k, what is the largest number i can get by wasting time in this manner?”
program input
the first line of the input contains an integer t (1 ≤ t ≤ 200), the number of test cases. each test case contains two integers n (1
≤ n ≤ 9) and k (0 ≤ k < 10n) where n is the number of digits this calculator can display k is the starting number.
program output
for each test case, print the maximum number that alice can get by repeatedly squaring the starting number as described.
sample input & output
input
output
calgary collegiate programming contest 2008
【思路一】
題目已經暗示電腦顯示會的數字出現循環，是以不妨一個一個的模拟，每次判斷新得到的數字是否以前出現過。如何判斷呢？一種方法
就是把所有計算出的數字放在數組中，然後一個一個的比較。這種方法每次判斷需要花費很長時間，相當慢，能否開一個數組visited，直接讀取visited[k]
來判斷整數k是否出現過，k(0 <= k < 10^9)的範圍很大，需要開辟的空間很大，嚴重浪費資源。在這種情況下我們可以利用stl的集合set。
【思路二】
這個方法還是不夠快的，第二種方法是用神奇的floyd判圈算法。
假設兩個小孩在一個可以無限向前跑的跑道上賽跑，同時出發，但其中一個小孩的速度是另一個小孩速度的兩倍。如果跑道是直的，跑得快的小孩永遠在前面，另一個小孩
永遠都追不上。但如果跑道有環，則跑的快的小孩将”追上“跑的慢的小孩。
【代碼2】
