UVa 11774 (置换 找规律) Doom's Day

时间：2022-08-02 08:34:54

我看大多数人的博客只说了一句：找规律得答案为(n + m) / gcd(n, m)

不过神题的题解还须神人写。。

We can associate at each cell a base 3-number, the log3(R) most significant digits is the index of the row of the cell and the log3(C) least significant digits is the index of his column.

What are the transformation now ?
position in row-major order is rC+c
position in column-major order is cR+r

We should shift down by log3(C) the most significant digits and shift up the least significant digits by log3(R).
C=3^6, R=3^4

now : rrrrcccccc (rrrr)(cccccc)
then: ccccccrrrr (cccc)(ccrrrr)

the first 4 digit are always the number of row (0-indexed) and the last 6 digit the number of column of the cell (0-indexed)
Now this process is valid for each possible r or c, so we can choose r=1 and c=0 and find a the length of this recurring cycle.
Calling L the length of this basic cycle, all other cycle are combination of this one so the only possible length are divisor of L, so the solution of our problem is (m+n)/L
rrrr=0001
cccccc=000000
day 0 : 0001000000 (0001)(000000)
day 1 : 0000000001 (0000)(000001)
day 2 : 0000010000 (0000)(010000)
day 3 : 0100000000 (0100)(000000)
day 4 : 0000000100 (0000)(000100)
day 5 : 0001000000 (0001)(000000)
For solving this problem we can find the the minimal x such that x*n mod (n+m)=0, this imply x=gcd(n, n+m)=gcd(n, m).
The solution of our original problem is (n+m)/x or (n+m)/gcd(n,m).

从0开始逐行给格子进行编号，然后每个格子用一个三进制数表示。还是以34×36的矩形为例，这样每个格子都可以用一个10位三进制数(R1R2R3R4)(C1C2C3C4C5C6)表示，而且高四位是行标，低六位是列标(行和列都是从0开始的)。

比如第1行第0列的格子的标号为(0001)(000000)，在执行操作的时候，第一行的数会填满第0~8列，所以这个数就变到了第0行第9列，表示成三进制数就是(0000)(000100)。

更一般地位于(R1R2R3R4)(C1C2C3C4C5C6)的格子的数会变到(C3C4C5C6)(R1R2R3R4C1C2)处。

也就是每次变换每个位置上的数字会右移4位。所以要使所有的数字都回到原位移动的最少次数就是(n + m) / gcd(n, m)

 #include <cstdio>

 typedef long long LL;

 LL gcd(LL a, LL b) { return b ==  ? a : gcd(b, a%b); }

 int main()

 {

     int T;

     long long m, n;

     scanf("%d", &T);

     for(int kase = ; kase <= T; kase++)

     {

         scanf("%lld%lld", &m, &n);

         printf("Case %d: %lld\n", kase, (m + n)/gcd(m, n));

     }

     return ;

 }

代码君

相关文章