题意
给你一个长为 (n) 的环，你可以把它断成任意 (k) 段 ((1 < k le n)) ，使得每一段的 (gcd) 都 (>1) 。
问总共有多少种方案，对于 (10^9 + 7) 取模。
(n le 10^5, 2 le a_i le 10^9) 。
题解
首先我们考虑序列上怎么做。
我们令 (dp_i) 为到 (i) 这个点的方案数， (pre_i) 为 (i) 向前延伸最长的那个点满足 ((displaystyle gcd_{j = pre_i}^{i} a[j]) > 1) 。
那么
显然这个 (dp) 可以用前缀和来进行优化成 (O(n)) 的。
至于 (pre_i) 的处理可以用线段树求区间 (gcd) ，然后用 two-pointers 来扫端点就行了，是 (O(n( log n + log V))) 的（ (displaystyle V = max_{i=1}^{n} a_i) ）。
好像利用 (gcd) 的一些奇怪势能分析可以证明。
然后如果成环的话，我们只需要多考虑一种情况也就是 (1,n) 相连。
对于这种情况，可以考虑枚举最后面有 (k) 个数和 (n) 相连就行了。
然后每次计算的时候，可以类似于前面 (dp) 的计算就行了，但是要注意一下，那个 ([pre_i = 1]) 要转化成后面 (k) 个数与前缀的 (gcd) 是否 (>1) 。（也就是我们强行把后 (k) 个数当做一个整体提到前面就行了）
然后这样直接做是 ((n^2 log V)) 的，不够优秀。
但是我们发现很多数其实没有什么本质区别的，也就是后缀 (gcd) 相同的一部分点可以一起计算。
这样的话，我们可以只在 (gcd) 转折处，以及 (0) 号点计算就行了（因为要考虑上 (1) 向后那一片 (gcd) 相同的数）。然后复杂度就是 (O(n log^2 V)) 的了。
因为一个点向一端不断延伸，它的 (gcd) 变换次数是 (O(log V)) 的，因为每次变化至少会对于其中一个指数 (-1) 。
还有个特殊情况，也就是全部 (gcd > 1) 的情况，需要将方案数 (- (n - 1)) 。（因为至少要分成 (1) 段）
最后就是 (O(n (log n + log V) log V)) 的。
总结
对于一类划分环计数的题目，可以考虑枚举最后面那一段和前面相连的长度，然后直接一遍 (O(n)) 计数。
对于有些关于 (gcd) 的题可以利用 (gcd) 变换次数不超过 (O(log V)) 来做。
代码
代码还是很好写的，可以参考一下。（其实博主参考了一下 ysgs 大佬的代码 ）
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << x << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}
inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x = 0, fh = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;
for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
return x * fh;
}
void File() {
#ifdef zjp_shadow
freopen ("gcd-on-a-circle.in", "r", stdin);
freopen ("gcd-on-a-circle.out", "w", stdout);
#endif
}
#define lson o << 1, l, mid
#define rson o << 1 | 1, mid + 1, r
const int N = 1e5 + 1e3, Mod = 1e9 + 7;
int a[N];
struct Segment_Tree {
int Gcd[N << 2];
void Build(int o, int l, int r) {
if (l == r) { Gcd[o] = a[l]; return ; }
int mid = (l + r) >> 1;
Build(lson); Build(rson); Gcd[o] = __gcd(Gcd[o << 1], Gcd[o << 1 | 1]);
}
int Query(int o, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return Gcd[o];
int mid = (l + r) >> 1;
if (qr <= mid) return Query(lson, ql, qr);
if (ql > mid) return Query(rson, ql, qr);
return __gcd(Query(lson, ql, qr), Query(rson, ql, qr));
}
} T;
inline int Add(int a, int b) { return (a += b) >= Mod ? a - Mod : a; }
int n, sum[N], dp[N], pre[N];
void Calc(int cur) {
sum[0] = 1;
For (i, 1, n) {
cur = __gcd(cur, a[i]);
if (cur > 1) dp[i] = sum[i - 1];
else dp[i] = Add(sum[i - 1], Mod - sum[max(0, pre[i] - 2)]);
sum[i] = Add(sum[i - 1], dp[i]);
}
}
int main () {
File();
n = read();
For (i, 1, n) a[i] = read(); T.Build(1, 1, n);
pre[1] = 1;
For (i, 2, n)
for (pre[i] = pre[i - 1]; pre[i] < i; ++ pre[i])
if (T.Query(1, 1, n, pre[i], i) > 1) break;
int Last = n, suf = 0, cur, ans = 0;
Fordown (i, n, 1) {
cur = __gcd(a[i], suf);
if (cur != suf || i == 1) {
Calc(suf); ans = Add(ans, Add(sum[Last], Mod - sum[i - 1]));
Last = i - 1; suf = cur;
}
}
printf ("%d
", Add(ans, (Mod - (T.Gcd[1] > 1 ? (n - 1) : 0))));
return 0;
}