题解：P14199 [ICPC 2024 Hangzhou R] Make It Divisible

myxRUC · 2025-10-23 20:37:53 · 题解

思路

备战 ICPC 武汉站，但是因为三个人有事无法 vp，因此今天单挑 2024 杭州站。这道题差不多是一道银牌题，快速切掉可以有银牌，因此设置为蓝题很合理。但是我在赛时没能写出这题，因为单调栈错了。又有一道铜牌构造 H 题不会，遗憾打铁。

算法：倍增，差分，单调栈。

有的大佬用了笛卡尔树，但是我不会这个高级数据结构，因此做法比较朴素。按照题目的要求，把每个数字加上 x 之后，在序列中任意选一个区间，如果区间内的每个数字能被区间内一个数字整除，就是满足题意。显然这个数字应该是区间内最小的数字，而且不难想到差分数组，如果 a 整除 c，b 整除 c，那么 a-b 显然整除 c。

但是如果枚举区间复杂度过高，由此我想到了之前南京站的一道题目，单独看每个数字，如果用单调栈找到他为最小值的最长区间，也就是对于每个数字 a_i 维护 l_i 和 r_i 就可以，然后算出这区间内的差分数组的 \gcd，可以用倍增计算，防止超时。再把他们存入集合，每次存 a_i 和 \gcd，因为之后要计算符合条件的 x。当然了，如果某个数字的 l_i 和 r_i 相等，就意味着他不会作为最小值存在于任何一个区间，除了他本身，因此不用计入集合。如果计算完毕，集合为空，说明所有的数字相等，那就是所有 x 均成立，输出答案即可。

在计算的过程中，我们要看哪个 x 在集合中的每个二元组里面都满足题意，也就是把每个二元组里面的 \gcd 所有因数和 a_i 作差，范围在 1 到 k 就成立。我们用映射来计数就行，一旦每个数字的计数等于集合的大小，就记录到答案里面，同时计数，最后输出就行。

代码

#include<iostream>
#include<stack>
#include<set>
#include<unordered_map>

using namespace std;
const int N = 50004, M = 20;
typedef pair<int, int>PII;

int a[N], l[N], r[N], lg[N], g[N][M];

inline int gcd(int a, int b) {
    while (b != 0) {
        int tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

int main(void) {
    int t, c = 0;
    cin >> t;
    while (t--) {
        set<PII>prm;
        unordered_map<int, int>calcu;
        int n, cnt = 0;
        long long k, ans = 0;
        c++;
        cin >> n >> k;
        lg[0] = -1;
        for (int i = 1; i <= n; i++) {
            lg[i] = lg[i >> 1] + 1;
            l[i] = r[i] = i;
        }

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

        for (int i = 1; i < n; i++) {
            g[i][0] = abs(a[i + 1] - a[i]);
        }

        for (int i = 1; i <= lg[n - 1]; i++) {
            for (int j = 1; j + (1 << i) - 1 < n; j++) {
                g[j][i] = gcd(g[j][i - 1], g[j + (1 << (i - 1))][i - 1]);
            }
        }

        stack<int>Q1;
        Q1.push(1);
        for (int i = 2; i <= n; i++) {
            if (a[Q1.top()] >= a[i]) {
                while (!Q1.empty()) {
                    auto k = Q1.top();
                    if (a[k] >= a[i]) {
                        r[k] = i - 1;
                        Q1.pop();
                    }
                    else {
                        break;
                    }
                }
            }
            Q1.push(i);
        }
        while (!Q1.empty()) {
            auto k = Q1.top();
            Q1.pop();
            r[k] = n;
        } 

        Q1.push(n);
        for (int i = n - 1; i >= 1; i--) {
            if (a[Q1.top()] >= a[i]) {
                while (!Q1.empty()) {
                    auto k = Q1.top();
                    if (a[k] >= a[i]) {
                        l[k] = i + 1;
                        Q1.pop();
                    }
                    else {
                        break;
                    }
                }
            }
            Q1.push(i);
        }
        while (!Q1.empty()) {
            auto k = Q1.top();
            Q1.pop();
            l[k] = 1;
        }
        for (int i = 1; i <= n; i++) {
            if (l[i] == r[i])continue;
            int lx = l[i], rx = r[i] - 1;
            int re = 0, len = lg[rx - lx + 1];
            re = gcd(g[lx][len], g[rx - (1 << len) + 1][len]);
            prm.insert({ re,a[i] });
        }
        if (prm.empty()) {
            cout << k << ' ' << (k + 1) * k / 2 << endl;
            continue;
        }

        for (auto i:prm) {
            int tk = i.first, mv = i.second;
            for (int j = 1; j * j < tk; j++) {
                if (tk % j == 0) {
                    if (j - mv > 0 && j - mv <= k) {
                        calcu[j - mv]++;
                        if (calcu[j - mv] == prm.size()) {
                            ans += (j - mv);
                            cnt++;
                        }
                    }
                    if (tk / j - mv > 0 && tk / j - mv <= k) {
                        calcu[tk / j - mv]++;
                        if (calcu[tk / j - mv] == prm.size()) {
                            ans += (tk / j - mv);
                            cnt++;
                        }
                    }
                }
                if ((j + 1) * (j + 1) == tk) {
                    if (j + 1 - mv > 0 && j + 1 - mv <= k) {
                        calcu[j + 1 - mv]++;
                        if (calcu[j + 1 - mv] == prm.size()) {
                            ans += (j + 1 - mv);
                            cnt++;
                        }
                    }
                }
            }
        }
        cout << cnt << ' ' << ans << endl;
    }
    return 0;
}