ICPC 2017 Latin American Regional J（思维）

[题目连接](https://vjudge.net/problem/Gym-101889J) ------------ 需要思考到： - 若$k$与$n$互质，那么必然会经过$n$个点回到原位 - 若$k$符合要求，$k$的倍数也必然符合要求 枚举$k$，$d=gcd(k,n)$，判断$d$是否满足要求即可 ------------ ```cpp #include <bits/stdc++.h> using namespace std; const int M=1e5+5; char s[M]; int ans,len,vis[M]; vector<int> vt; set<int> st; int check(int d) { if(vis[d]!=-1)return vis[d]; st.clear(); for(int i=0;i<vt.size();i++) { int p=vt[i]; st.insert(p%d); if(st.size()==d)return vis[d]=0; } return vis[d]=1; } int main() { scanf("%s",s+1); len=strlen(s+1); for(int i=1;i<=len;i++)if(s[i]=='P')vt.push_back(i); if(vt.empty())return 0*printf("%d\n",len-1); for(int i=2;i<len;i++) { vis[i]=-1; int d=__gcd(i,len); if(d>1)ans+=check(d); } printf("%d\n",ans); return 0; } ```