1. a[i] == a[i+k*n]
2. a[i] >= a[i+k*s]
=> a[i] >= a[i+k*g] ( g = gcd(n, s) )
枚举g， 当一个子序列合法时，当且仅当序列中的每一个数为它所在环中的最大值。
枚举位置i，得到关于i为终点的最长合法子序列。
枚举长度s，每一个小于等于s的长度l对s的贡献为1，当且仅当gcd(n, s) == g
再次枚举位置i，得到每个位置对答案的贡献。
代码：
#include<bits/stdc++.h> #define pb push_back #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int, int> PII; const double PI = acos(-1.0); const double eps = 1e-10; int dcmp(double x) { if(fabs(x) < eps) return 0; else return x<0?-1:1; } const int INF = 0x3f3f3f3f; const int N = 2e5+5; bool ismx[2*N]; int a[2*N], dp[2*N]; ll cnt[N]; int main() { int n; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); a[i+n] = a[i]; } ll ans = 0; for(int g = 1; g <= n; g++) if(n%g == 0) { for(int i = 0; i < g; i++) { int maxa = a[i]; for(int j = i; j < 2*n; j += g) maxa = max(maxa, a[j]); for(int j = i; j < 2*n; j += g) ismx[j] = maxa==a[j]; } for(int i = 0; i < 2*n; i++) { dp[i] = ismx[i]; if(i && ismx[i]) dp[i] += dp[i-1]; dp[i] = min(dp[i], n-1); } cnt[0] = 0; for(int i = 1; i < n; i++) { cnt[i] = cnt[i-1]; if(i%g == 0) cnt[i] += __gcd(i/g, n/g)==1; } for(int i = n; i < 2*n; i++) ans += cnt[dp[i]]; } cout << ans << endl; return 0; }