题目地址：https://codeforces.com/gym/101889

题目：

圆上有N个点，编号从0开始，R表示石头，P表示水池(不可跳到水池)。

问有多少个k，1≤k≤N-1，使得青蛙能某个点起跳并回到这个点，且途中不经过水池，若当前编号为i，下一跳编号为（i+k）%N

解题思路：

又回到起点，最少跳了一圈，最多跳了N圈，令途中经过的点的数目为mk，m是跳的次数，则有mk=tN，mk必须是N的倍数。

因为只需要回到起点一次，所以目的是要找一个最小的m使得mk是N的倍数。

先不考虑有水池的情况。

（1）当k是N的因子时，m=N/k，途经了圆上的部分点，且沿着圆跳完一圈之后必定会到起点，起点可以只从0~k-1枚举，因为从≥k之后枚举的话在圆上跳的时候还会经过k之前的点，是等价的。（不过剪枝之后这个对时间复杂度并无影响）

（2）当k和N互质时，m=N，此时必定途经了圆上的所有点

（3）当k不和N互质且不是N的因子时， 即gcd（N,k）!=1时 ，m=N*k/gcd(N,k)，途经了圆上的部分点，此时的是（1）中k的整数倍（>1的整数倍）

还可以发现一个重要的性质，若k满足题目的条件，那么2k,3k...必定也满足条件，可以直接标记。

故只需要考虑（1）（2），而1和N互质，其他和N互质的数也是1的倍数，最终只需要考虑（1），1也是N的因子。

最终思路：

1~N-1得到N的因子们，判断每个因子是否满足条件，若满足条件，它的倍数必定也满足条件，加上标记和剪枝。其实1～N-1最终每个数都考虑到了，但并非单纯的暴力。

训练的时候想到了红字的性质，但是没想到因子，其实是没有完全利用到这个条件。

ac代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
char s[maxn];
bool vis[maxn] = {false};
vector<int> fac;
int n;
bool judge(int i, int k)
{
    int pos = i;
    while(1)
    {
        pos = (pos+k) % n;
        if(s[pos] == 'P') return false;
        if(pos == i) return true;
    }
}
int main()
{
    scanf("%s", s);
    n = strlen(s);
    for(int i = 1; i < n; i++)
        if(n % i == 0) fac.push_back(i);
    int ans = 0;
    for(int i = 0; i < fac.size(); i++)
    {
        //即使fac[i]被标记了，但是它的其他倍数可能未被标记
        for(int j = 0; j < fac[i]; j++)//只跳了一圈
        {
            if(s[j]=='R' && judge(j, fac[i]))
            {
                for(int p = 1; p*fac[i] < n; p++)
                {
                    if(!vis[p*fac[i]])
                    {
                        vis[p*fac[i]] = true;
                        ans++;
                    }
                }
                break;
            }
        }
    }
    printf("%d\n", ans);
    return 0;
}