We all know about the legend oftower of Hanoi. It is said that the world will end after finishing the puzzle.What we don't know is another legend about when the world will end which is verifiedby the scientists.
It is all about a 3^n * 3^m grid.Initially the grid is filled with 1 to 3^(m+n) in row major order. At each stepthe puzzle is rearranged by reading it in row major order and putting them incollumn major order. See the following examples.
1
2
3
to
1
10
19
4
5
6
2
11
20
7
8
9
3
12
21
10
11
12
4
13
22
13
14
15
5
14
23
16
17
18
6
15
24
19
20
21
7
16
25
22
23
24
8
17
26
25
26
27
9
18
27
1
2
3
to
1
4
7
4
5
6
2
5
8
7
8
9
3
6
9
Now every day the puzzle is rearrangedonce. The legend says if someday initial configuration returns the world willend. Now you are wondering when the world is going to end.
Input
Input starts with a linecontaining number of test cases T ≤ 10000. Each test case containstwo positive integer m ≤ 10^9and n≤ 10^9.
Output
For each case print one linecontaining days before dooms day. The input will be such that this number fitsin 64 bit unsigned integer.
SampleInput Outputfor Sample Input
5
1 1
1 2
3 1
2 2
98876767 12234
Case 1: 2
Case 2: 3
Case 3: 4
Case 4: 2
Case 5: 98889001
Problemsetter:Tanaeem Md. Moosa
SpecialThanks to: Jane Alam Jan
題意：往3^n * 3^m的格子裡1到3^(n+m) 的數，每次的操作是：將數按行優先拿出來，再按列優先放進去，求多少次後回到初始狀態
思路：規律ans=(a+b)/gcd(a, b);
#include#include #include #include using namespace std; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } int main() { int t, a, b, cas = 1; scanf("%d", &t); while (t--) { scanf("%d%d", &a, &b); printf("Case %d: %d\n", cas++, (a+b)/gcd(a, b)); } return 0; }
