首先可以想到暴力吧。 每一轮回到 nnn 显然需要跳 ngcd⁡(i,n)\dfrac{n}{\gcd(i,n)}gcd(i,n)n​ 次。 那么不妨直接暴力。这样是调和级数级别的复杂度。 但是 gcd⁡\gcdgcd 在大部分情况下很小，所以这个调和级数会被卡成 n2n^2n2 级别。 那么想到记忆化。由于答案是 ngcd⁡(i,n)×i=1nai, i≡0 ( mod  gcd⁡(i,n))\dfrac{n}{\gcd(i,n)} \times \min\limits_{i=1}^n a_i, \space i \equiv 0 \space (\bmod \...