题解：P13836 微观戏剧（Constructive ver.）

yanxu_cn · 2025-08-27 11:42:56 · 题解

核心知识点：没有知识点，纯观察。

本题还是相当有意思的。

对于极小的数据，我们最好先看一下样例。

样例给了我们一点启发：

接下来得出一个重要的结论：f(x_0,y_0)=\min\{\operatorname{lcm}\{x_0,y_0\},x_0+y_0\}。也挺好理解：要不就是 x_0 与 y_0 之间直连，要不就是到 1 中转一下，也挺明白。

这个结论虽然可以说是 100% 正确的，但是大家有没有注意到对于 x_0=1（y_0=1 也一样，我们先假设 x_0=1）这个题目有一个特殊性质：f(x_0,y_0)=y_0（事实上，之所以特殊就在于 1 是所有的正整数的因数之一，但是这里其实有点问题，因为这个时候“去 1 中转一下”的情况就不是 x_0+y_0 的代价了而是 y_0 的代价）。

这个事实上对于 z\ge2 都是成立的，但是这里还要考虑下这个题目的数据范围限制，所以对于 2\le z\le10^{18} 这么做都是没什么问题的。

那么问题又到了对于 10^{18}<z<2\times10^{18} 的情况了是吧。

我们有一个很简单的结论，就是只要这两个数其中一个数不是另一个数的因数，那么就一定存在 x_0+y_0\le\operatorname{lcm}(x_0,y_0)，所以简单的，我们输出两个比较接近的数就行。但是注意到不能超过 10^{18}，所以还是有点讲究，比如按照这样的写法就没有问题，也不必判定奇偶性，挺方便：cout<<(n+2)/2<<' '<<n-(n+2)/2<<'\n';。

代码实现比较丑，不放了。