J - Jumping frog Gym - 101889J（gcd，类似置换）

题意：
R可与走，P不可以走。
可以任选起点，每步的长度为k。
求问存在多少k，使得你最后可以跳回起点。
从i跳一步后会变成(i+k)%n

思路：
感觉和之前写过的置换很像，也是在环上跳。

对于所跳的步长k，如果gcd(n,k)=1，那么实际就是要遍历每一个点，必须得满足所有点都是R。
否则的话，最终要跳$n?k/gcd(n,k)/k=n/gcd(n,k)$步。这个部分的个数等于n的约数的个数，不会很多。

所以我们枚举n的所有约数（互质直接判断），然后枚举起点模拟一直跳就好了。
因为选择了一个起点后，会遍历$n/gcd(n,k)$个点。起点右移，又会遍历$n/gcd(n,k)$个点，选择了前$gcd(n,k)$个点就遍历了所有点，因此只需要选这前$gcd(n,k)$个点。

（图凑合看吧，就是表达一个意思）
此时k=8,n=12
0->8->4->0
1->9->5->1
2->10->6->2
3->11->7->3

#include <bits/stdc++.h>
#define lson (id<<1)
#define rson (id<<1|1)
using namespace std;
const int maxn = 1e5+10;
typedef long long ll;char s[maxn];int gcd(int n,int m) {
    return m == 0 ? n : gcd(m,n % m);
}int main() {
    scanf("%s",s);int n = strlen(s);int flag = 1;for(int i = 0;i < n;i++) {
    if(s[i] == 'P') {
    flag = 0;break;}}int ans = 0;for(int i = 1;i < n;i++) {
    int num = gcd(i,n);if(num == 1) {
    if(flag) {
    ans++;}} else {
    bool ok = 1;for(int j = 0;j < num;j++) {
    ok = 1;int sta = j;while(1) {
    if(s[sta] == 'P') {
    ok = 0;break;}sta = (sta + i) % n;if(sta == j) break;}if(ok) break;}if(ok) ans++;}}printf("%d\n",ans);return 0;
}