非常的妙啊, 感觉

题意:

定义一个高度为x的金字塔序列为如下的无限长序列:

\{1,2…x-1,x,x-1,x-2…3,2,1,2,3\}

现在给出 nm,令 A是高度为 x的金字塔序列, B是高度为 y的金字塔序列, 求有多少个不同的数对 (x, y), 满足\exists i \in Z, s.t.A_i = x, B_i = y

分析:

这道题目我们可以考虑将每一个i所对应的A_iB_i分别为横纵坐标, 描绘在笛卡尔坐标系上
那么我们可以发现它就是一个”光路图”, 碰到墙壁之后就反弹, 一直到碰到4个棱角中的一个的时候就停止, 如图 (证略)



为了下文的方便起见, 我们都将n,m减去1来看, 也就是(1,1) ~ (n,m)这块

因为题目要求我们找出这条路径上有多少的点, 如果不考虑重复, 其实我们的答案就是可以变成\frac{a\cdot b}{gcd(a,b)} = lcm(a, b) 就好了!

考虑 (镜像法, 对于反射的位置进行对称使得它变成一条直线)

n = k_1d, m=k_2d, (k1, k2) = 1

  • 考虑d = 1的情况,

\ \ \ \ \ 我们会发现这条反弹路径的下一个点一定是横纵坐标均变化一, 也就是一直都会在横纵坐标之和为偶数的节点上, 那么不难发现对于一个网格图中的任意一个方格有且仅有2个点满足该类情况.

也就是说: 如果路径要穿过这个方块一定是经过了这两个点连线的对角线, 且每个方格的对角线最多只会被经过一次, 所以经过的方格数 \leq a \cdot b

因为总的路径长度是\frac{a\cdot b}{gcd(a,b)} = a \cdot b 那么结合上述, 也就是说每个方格都会被访问一遍, 所以这种情况下的答案就是所以格点满足横纵坐标之和为偶数的数量, 即\lceil \frac{(a + 1) \cdot (b + 1)}{2}\rceil

  • d>1

那么对于那一些的情况, 我们就可以抽象成(k_1,k_2)的局面扩大了d倍, 那么每一个d \cdot d的块里在路径上就会 多出 (d – 1)个点, 所以答案加上(d-1) \cdot k_1*k_2 就好了

Code:

class PyramidSequences {
public:
    long long distinctPairs( int N, int M );
};
typedef long long LL;

int gcd(int a, int b)
{
    return (!b) ? a : gcd(b, a % b);
}
long long PyramidSequences::distinctPairs(int N, int M) {
    LL n = N - 1, m = M - 1, d = gcd(n, m);
    n /= d, m /= d;
    return 1LL * (d - 1) * (n * m) + 1LL * ((n + 1) * (m + 1) + 1) / 2;
}

Leave a Reply