这题完全体现了我的 数学推导 能力有多差。

---

中间还被 alpha 教育了，我不会算这个复杂度/kk

\[O(\sum_{i=1}^{n} \sum_{j|i}\sum_{k|\frac{i}{j}}1)=O(n\log^2n) \]

---

根据一些等价我们得到下面的式子。（上面是字符串和图论的部分，下面就全是数学推导了）

\[ans\times k^n=\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}k^{\max{\gcd(i,j), i+j-n}} \]

然后有一个不太能扩展的 \(O(n\log^2n)\) 做法。

考虑枚举 \(\gcd(i,j)\) 和 \(i+j\)，然后计算同时满足 \(i,j\) 组数。

\[\begin{aligned} ans\times k^n&=\sum_{s=2}^{2n-2}\sum_{d|s}\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[\gcd(i,j)=d][i+j=s]\\ &=\sum_{s=2}^{2n-2}\sum_{d|s}\sum_{i=1}^{n-1}[\gcd(i,s-i)=d]\\ &=\sum_{s=2}^{2n-2}\sum_{d|s}\sum_{i=1}^{[\frac{n-1}{d}]}[\gcd(i,\frac{s}{d}-i)=1]\\ &=\sum_{s=2}^{2n-2}\sum_{d|s}\sum_{i|\frac{s}{d}}\mu(i)\sum_{j=ik}1 \end{aligned} \]

然后上面的式子有一个缺陷，就是 \(i,j\) 的范围没有表示。

\[1\le i\le n-1\\ 1\le s-i\le n-1\\ \Rightarrow s+1-n\le i\le s-1\\ \]

然后令 \(a=\max\{1,\frac{s}{d}-[\frac{n-1}{d}]\},b=\min\{\frac{[n-1]}{d},\frac{s}{d}-1\}\)，有最终的式子 \(ans\times k^n=\sum_{s=2}^{2n-2}\sum_{d|s}\sum_{i|\frac{s}{d}}\mu(i)([\frac{b}{i}]-[\frac{a-1}{i}])\)。

还有一个常见的 \(O(n\logn)\) 算法和一个 \(O(n)\) 算法。看懂了但是不想写了（咕咕有空就补），可以在下面的题解里看到。

reference

木xx木大的 luogu 题解