GYM 101889J（枚举、环上gcd）

答案只有n - 1种暴举即可，对于每种，gcd是一那踩雷稳了，否则看雷的分布有没有把模余占满。

const int maxn = 1e5 + 5;
int n, ans;
char str[maxn];
vector<int> pos;
bool vis[maxn], yes[maxn];
bool ok(int t) {
if (vis[t]) return yes[t];
vis[t] = true;
set<int> s;
for (int i : pos) {
s.insert(i % t);
if (s.size() == t)
return yes[t] = false;
}
return yes[t] = true;
}
int __gcd(int a, int b) {
return b ? __gcd(b, a % b) : a;
}
int main() {
scanf("%s", str);
n = strlen(str);
for (int i = 0; str[i]; ++i) {
if (str[i] == 'P') {
pos.push_back(i);
}
}
if (pos.size() == 0)
ans = n - 1;
else {
for (int i = 1; i < n; ++i) {
int tmp = __gcd(i, n);
if (tmp > 1) {
if (ok(tmp))
ans++;
}
}
}
writeln(ans);
return 0;
}