A96808.函数求和 题解

这题需要一定的数学基础。

显然，一个 $A_i$ 只可能对应一个 $A_{i+1}$，且注意到 $f(A_i^2,M)$ 一定 $\le M-1$，所以 $A$ 一定有循环部分，即一定能找到一组 $p,q$，满足 $A_p= A_q$。

证明上方命题的方法如下：

用反证法。

引理：如果有 $n$ 个东西要放进 $m$ 个盒子，并且 $n > m$，那么至少有一个盒子里会有超过一个东西。（鸽巢原理）

我们发现，该函数的取值范围为 $[0,M-1]$，注意到可以带入上方原理，$n = ∞$（因为可以无限算），$m = M$，$M \le 10^5$，所以一定存在循环部分。

我们就可以根据上方证明结果做这道题，复杂度 $O(L)$，$L$ 为循环部分长度。