这题需要一定的数学基础。 显然，一个 AiA_iAi 只可能对应一个 Ai+1A_{i+1}Ai+1 ，且注意到 f(Ai2,M)f(A_i^2,M)f(Ai2 ,M) 一定 ≤M−1\le M-1≤M−1，所以 AAA 一定有循环部分，即一定能找到一组 p,qp,qp,q，满足 Ap=AqA_p= A_qAp =Aq 。 证明上方命题的方法如下： 用反证法。 引理：如果有 nnn 个东西要放进 mmm 个盒子，并且 n>mn > mn>m，那么至少有一个盒子里会有超过一个东西。（鸽巢原理） 我们发现，该函数的取值范围为 [0,M−1][0,M-1][0,M−1]，注意到可以带入上方原理，n=∞n = ∞n=∞（因为可以无限算），m=Mm = Mm=M，M≤105M \le 10^5M≤105，所以一定存在循环部分。 我们就可以根据上方证明结果做这道题，复杂度 O(L)O(L)O(L)，LLL 为循环部分长度。