# 烤墨鱼的置换: 题解

出题人解法：分解置换环，对环长分解质因数，保留每个质因子的最大指数。Codex（GPT-6）整理单组输入、边界、证明及 C++17 实现；试除到平方根的写法也见于出题人的配套讲解。

## 复原次数是环长的最小公倍数

每个位置恰有一个后继和一个前驱，故置换由互不相交的环组成。长度为 $\ell$ 的环上，元素每次前进一格；因元素互不相同，恰好在操作次数是 $\ell$ 的倍数时整个环复原。因此所有环同时复原的最小正次数，就是全部环长的最小公倍数。

依次从尚未访问的位置出发，沿后继走到已访问位置，计数得到环长。程序用后继零值标记访问；必须先保存后继，再清零，才能继续沿环行走。每个位置恰好访问一次，单点环的长度为一。

## 在取模前保留质因子信息

若环长的质因数分解为 $\ell=\prod p^{e_p}$ ，最小公倍数中 $p$ 的指数是所有环上的最大 $e_p$ .用数组维护这些最大值，最后逐个乘入质因子并模 $998244353$ .不能先对环长或中间最小公倍数取模，再对余数求最小公倍数；取模会丢失整除信息。

试除时从二开始，对每个因子除尽并记录次数。若剩余值小于当前因子的平方，就停止；剩余值大于一时必为一个质因子，补记指数一。较小质因子已被除尽，所以非质数候选不会产生错误的因子。最大指数给出的整数被每个环长整除，且整除任何公倍数，因此是最小公倍数。最后仅对其乘积取模，答案正确。

## 复杂度与方案选择

环长之和为 $N$ .一个长度为 $\ell$ 的环的试除及除法次数可以粗略界为 $O(\ell)$ ，故所有环的分解总时间为 $O(N)$ ，加上访问环和扫描指数数组，整体时间、空间均为 $O(N)$ .这也解释了按长度逐个试除的版本仍有线性总上界，平方根截止减少无效试除，而不改变这里的整体阶。

乘法前答案小于模数，因子不超过 $N$ ，乘积小于 $10^{15}$ ，64 位整数足够。全是单点环时乘积保持为一，符合最小正次数要求。

[std.cpp](std.cpp) 使用上述方法。逐次模拟可能依赖极大的真实答案；最小质因子筛需要额外预处理，未改善本题已有的线性总上界；任意精度整数最小公倍数适合作为独立核对，但不是固定宽度整数实现的改进。