题目链接
题目大意
一只青蛙在长度为N的字符串上跳跃，“R”可以跳上去，“P”不可以跳上去。
字符串是环形的，N-1和0相连。
青蛙的跳跃距离K的取值范围是[1, N-1]，选定K之后不可改变。
要求青蛙最后能跳回起点（起点可以是0-N-1的任意一个位置），问K的取值有多少种选择。
(3≤N≤{10}^5)。
题目思路
主要是要发现每一次走的步数一定是gcd(i,n)
然后发现gcd只有log(n)(可能多一些，但是没多太大)
然后O(n) check
代码
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#define fi first
#define se second
//#define int long long
#define debug printf(" I am here
");
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const ll INF=0x3f3f3f3f3f3f3f3f;
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-10;
char s[maxn];
int n;
int vis[maxn];
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
bool check(int x){
for(int i=1;i<=x;i++){
bool flag=1;
for(int j=i;j<=n;j+=x){
if(s[j]=='P'){
flag=0;
break;
}
}
if(flag) return 1;
}
return 0;
}
signed main(){
memset(vis,-1,sizeof(vis));
scanf("%s",s+1);
n=strlen(s+1);
int ans=0;
for(int i=1;i<=n-1;i++){
int x=gcd(i,n);
if(vis[x]==-1){
if(check(x)){
vis[x]=1;
}else{
vis[x]=0;
}
}
ans+=vis[x];
}
printf("%d
",ans);
return 0;
}