题目

QOJ 9738。

引理

关于 GCD，满足 gcd⁡(a,b)=gcd⁡(a,∣b−ka∣)\gcd(a,b)=\gcd(a,|b-ka|)。

只需证明：

  1. gcd⁡(a,b)=gcd⁡(a,b−a),a<b\gcd(a,b)=\gcd(a,b-a),a<b：

    令 d=gcd⁡(a,b)d=\gcd(a,b)，那么 a=k1d,b=k2da=k_1d,b=k_2d，于是 d∣ad\mid a 且 d∣b−ad\mid b-a，于是 gcd⁡(a,b)∣gcd⁡(a,b−a)\gcd(a,b)\mid \gcd(a,b-a)

    同理可证 gcd⁡(a,b−a)∣gcd⁡(a,b)\gcd(a,b-a)\mid \gcd(a,b)，于是这两个数字相等。

  2. gcd⁡(a,b)=gcd⁡(a,a−b),a>b\gcd(a,b)=\gcd(a,a-b),a>b：

    证明同上。

于是，我们可以进行若干次第一条结论得到 gcd⁡(a,b)=gcd⁡(a,b−ka),b−ka>0\gcd(a,b)=\gcd(a,b-ka),b-ka>0；

如果 b−ka>0b-ka>0 且 b−(k+k′)a<0b-(k+k')a<0，可以有 gcd⁡(a,b−ka)=gcd⁡(a,k′a−(b−ka))=gcd⁡(a,(k+k′)a−b)\gcd(a,b-ka)=\gcd(a,k'a-(b-ka))=\gcd(a,(k+k')a-b)。

这就证明了 gcd⁡(a,b)=gcd⁡(a,∣b−ka∣)\gcd(a,b)=\gcd(a,|b-ka|)。

思路

一个 trivial 的思路是，用 O(n2)O(n^2) 的复杂度枚举所有区间，找到符合条件的 xx，并给它们求交集。

观察一下定义，对于一个合法的 [l,r][l,r]，对所有的 l≤i≤rl\le i\le r，都有 ad∣aia_d\mid a_i，那么 ada_d 一定是 min⁡i=lrai\min_{i=l}^r a_i。

如果 [l,r][l,r] 是一个 divisible interval，它以 ada_d 为最小值的子区间一定也是 divisible interval。

而题目要求所有的子区间都应该是 divisible interval，于是，对于最小值为 ada_d 的所有区间，只需要使极大的那一个满足要求就行。

又因为，所有的子区间一定以某个 aia_i 为最小值。所以我们反过来枚举 ada_d，找到它控制的所有区间，并且只要使极大的那个满足就行。

找到每个 ada_d 控制的极大区间，可以用单调栈来实现。官方题解是笛卡尔树，这两个做法本质上是一样的。

这里有一个转化，∀l≤i≤r,ad∣ai⇔gcd⁡(al,al+1,…,ar)=ad\forall l\le i\le r, a_d\mid a_i\Leftrightarrow \gcd(a_l,a_{l+1},\dots,a_r)=a_d。

现在考虑 xx 的问题：

gcd⁡(al+x,al+1+x,…,ar+x)=gcd⁡(ad+x,al+x,al+1+x,…,ar+x)=gcd⁡(ad+x,∣al−ad∣,∣al+1−al∣,…,∣ar−ar−1∣)=gcd⁡(ad+x,gcd⁡(∣al−ad∣,∣al+1−al∣,…,∣ar−ar−1∣))=gcd⁡(ad+x,gd)=ad+x\begin{aligned} \gcd(a_l+x,a_{l+1}+x,\dots,a_r+x)&=\gcd(a_d+x,a_l+x,a_{l+1}+x,\dots,a_r+x)\\ &=\gcd(a_d+x,|a_l-a_d|,|a_{l+1}-a_l|,\dots,|a_r-a_{r-1}|)\\ &=\gcd(a_d+x,\gcd(|a_l-a_d|,|a_{l+1}-a_l|,\dots,|a_r-a_{r-1}|))\\ &=\gcd(a_d+x,g_d)\\ &=a_d+x \end{aligned}

我们可以通过 ST 表快速求出 gdg_d。特殊地，对于 l=rl=r 的情况，令 gd=0g_d=0，也就是这个式子恒成立。

如果 gd≠0g_d\neq 0，那么一定有 ad+x∣gda_d+x\mid g_d，于是我们可以枚举 gdg_d 的因数，初步找到所有候选的 xx。

因为我们的答案是对所有 xx 的集合取交集，所以可以先找到一组答案的超集，然后检查它们是不是都合法。

这样做的复杂度是 O(nmax⁡d(V))O(n\max d(V))，其中 V=109V=10^9，max⁡d(V)=1344\max d(V)=1344。

实现

实现上来说，如果 n=1n=1，自然所有的 xx 都合法；如果对于最大的区间 gd=0g_d=0，说明每一个数都是 ada_d。这是因为只有所有数都是 00，gcd⁡\gcd 的结果才会是 00，观察 gdg_d 的定义不难得到所有的数都是 ada_d。此时也是所有的 xx 都合法。

还有一个需要注意的，就是枚举因数和质因数的方法并不相同，我一开始写成了枚举质因数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 5e4+10, K=20;
int a[N], n, k, L[N],R[N];
int st[K][N], lg2[N];

void breakdown(unordered_set<int>& v, int x, int ad) {
    for (int i = 1; i*i <= x; i++) {
        if (x % i == 0) {
            if (1 <= i - ad && i - ad <= k) v.insert(i - ad);
            if (1 <= x/i - ad && x/i - ad <= k) v.insert(x/i - ad);
        }
    }
}

int query(int l, int r) {
    int k = lg2[r-l+1];
    return gcd(st[k][l], st[k][r-(1<<k)+1]);
}

void solve() {
    cin >> n >> k;
    for (int i = 2; i <= n; i++) lg2[i] = lg2[i>>1] + 1;

    int mn = 1e9;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mn = min(mn, a[i]);
    }

    stack<int> stk;
    for (int i = 1; i <= n; i++) {
        while (stk.size() && a[stk.top()] >= a[i]) stk.pop();
        if (stk.size()) L[i] = stk.top() + 1;
        else L[i] = 1;
        stk.push(i);
    }
    stack<int>().swap(stk);
    for (int i = n; i >= 1; i--) {
        while (stk.size() && a[stk.top()] >= a[i]) stk.pop();
        if (stk.size()) R[i] = stk.top() - 1;
        else R[i] = n;
        stk.push(i);
    }
    
    for (int k = 0; k < K; k++) {
        for (int i = 1; i+(1<<k)-1 <= n; i++) {
            if (k == 0) st[k][i] = abs(a[i] - a[i-1]);
            else st[k][i] = gcd(st[k-1][i], st[k-1][i+(1<<(k-1))]);
        }
    }

    unordered_set<int> ans;
    if (n == 1) {
        cout << k << ' ' << 1ll * k * (k+1) / 2 << '\n';
        return;
    }

    int g = query(2, n);
    g = gcd(g, abs(a[1] - mn));
    if (g == 0) {
        cout << k << ' ' << 1ll * k * (k+1) / 2 << '\n';
        return;
    }
    breakdown(ans, g, mn);

    for (int i = 1; i <= n; i++) {
        if (L[i] == R[i]) continue;
        g = query(L[i]+1, R[i]);
        g = gcd(g, abs(a[L[i]] - a[i]));

        for (auto it = ans.begin(); it != ans.end(); ) {
            int x = *it;
            if (gcd(g, a[i] + x) != a[i] + x) it = ans.erase(it);
            else it++;
        }
    }
 
    int sum = 0;
    for (int x: ans) sum += x;
    cout << ans.size() << ' ' << sum << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}