codeforces 1806C解析C++

题目链接：https://codeforces.com/problemset/problem/1806/C

题意：

给定一个长度为 $n$ 的字符串 $s$ 和一个整数 $k$，每次操作可以将字符串中的一个字符改为另一个字符（不同位置可以改成不同的字符），问最少需要多少次操作才能将字符串变为 “No”（即不能再划分为至少 $k$ 个相同的子串）。

解法：

首先，我们可以将字符串 $s$ 划分成若干个相同的子串，设每个子串的长度为 $len$，则 $n=kl$，其中 $l$ 为每个子串的长度。

因此，我们可以考虑暴力枚举每个子串的长度 $l$，那么 $k$ 也可以通过 $n$ 和 $l$ 推出，即 $k=\frac{n}{l}$。

接下来，我们需要判断这个 $l$ 是否可行，即判断字符串 $s$ 是否能被划分成若干个长度为 $l$ 的子串。我们可以使用哈希来快速判断。对于每个 $l$，我们将字符串 $s$ 分成 $k$ 个子串，分别计算每个子串的哈希值，如果所有子串的哈希值都相同，则说明可以划分成若干个长度为 $l$ 的子串，否则不行。

最后，我们只需要统计所有可行的 $l$ 中最小的操作次数即可。

时间复杂度为 $O(n\log n)$。

代码实现：