C++ 算法题：魔镜项链的最小长度

题目描述 国王有一个魔镜，可以把任何接触镜面的东西变成原来的两倍——只是，因为是镜子嘛，增加的那部分是反的。比如一条项链，我们用'AB'来表示，不同的字母表示不同颜色的珍珠。如果把'B'端接触镜面的话，魔镜会把这条项链变为'ABBA'。如果再用一端接触的话，则会变成'ABBAABBA'（假定国王只用项链的某一端接触魔镜）。给定最终的项链，请编写程序输出国王没使用魔镜之前，最初的项链可能的最小长度。

输入描述 只有一个字符串，由大写英文字母组成（字母数<=100000），表示最终的项链。

输出描述 只有一个整数，表示国王没使用魔镜前，最初的项链可能的最小长度。

样例1 输入 'ABBAABBA' 输出 2

提示字母数<=100000 。

解题思路： 根据题意，国王使用魔镜时，每次都会在项链的某一端接触魔镜。设最初的项链长度为n，则经过一次使用魔镜，项链的长度将变为2n-1或2n，其中2n-1是因为增加的那部分是反的。因此，国王使用魔镜的次数越多，项链的长度就会越长。

假设最终的项链长度为m，那么国王使用魔镜的次数就是m/n。因为题目要求最初项链的长度最小，所以我们要找到最小的n，使得m/n为整数。也就是找到m的所有因子中最小的一个。

具体实现步骤如下：

读取输入的最终项链字符串。
获取最终项链的长度m。
从1到m的范围内遍历，找到m的所有因子。
在因子中找到最小的一个，作为最初项链的长度n。
输出n作为结果。

时间复杂度分析： 假设最终项链长度为m，那么找到m的所有因子的时间复杂度为O(m)。因此，总的时间复杂度为O(m)。由于题目给出的约束为m<=100000，所以算法的时间复杂度是可接受的。