LinhoNotes

外观

假期练习 #4 ​

Topic 1 GCD（最大公约数）性质 ​

  • gcd(a,b)=gcd(a,b−a)
  • gcd(a1,a2,...,an)=gcd(a1,d2,d3,...dn)
  • 差分数组可能有负数，应用这个性质的差分数组需要取绝对值

应用例 1 ​

给定 n 个正整数 ai，问它们至少同时加多少，可以使得它们的最大公约数大于 1，若不存在，则输出−1

  • 我们可以将化为差分数组： a1+k,a2−a1,a3−a2,…,an−an−1
  • 注意到除了第一项之外的数是不变的，也就是说，我们只需要让第一项和后面部分的 gcd 不互质即可
  • 这一步可以通过枚举因数来实现
  • 最后要注意的一点是所有数相同的情况，若所有数都是 1，那么输出 1；否则输出 0

应用例 2 ​

M. Make It Divisible

赛时想了很多性质，结果基本没用上，还一头撞死在没学过的数据结构上了

赛后看题解，补了笛卡尔树，这个数据结构感觉不很复杂，但是能很好地把序列不断按照最小（大）值分块，后续看看其他的笛卡尔树应用例熟悉一下这玩应

注意到合法的答案有如下性质：

  • 对于任何一个区间，都有其最小值等于其区间最大公约数
  • 用 gcd 的差分性质转化，等价于其最小值能整除其差分数组（去除首项）的最大公约数
  • 同时，109 以内 的数最多只可能有 f=1344 个因数

于是我们考虑从整个数组开始，对这个性质做 check ，每次检查完一个区间后，将区间以当前最小值为界分成左右两个子区间，并对其中 size≥1 的子区间继续 check ，由这个检查方式可以自然联想到使用笛卡尔树来快速处理出区间

最开始，我们可以直接取整个序列上满足条件的 x 放入一个 vector 中，可知 x 的数量不会超过 f=1344

在这之后，每次下放区间，检查 x+min(l,r) 是否能整除区间差分数组的最大公约数 gcd(l,r)

特别地，当初始数组全部相等的时候，差分数组全部为零，任何大小符合要求的 x 均满足条件，需要特判处理

AC 代码 ​

c++
#include <bits/extc++.h>
#define OOO cout << ">>>>";       // 调试标识
#define CY cout << "YES" << endl; // 输出宏
#define CN cout << "NO" << endl;  // 输出宏

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rnd(time(0));
typedef long long ll;
typedef uint64_t ull;
template <typename T> using vct = vector<T>;
template <typename T> using v2ct = vector<vector<T>>;
template <typename T> using v3ct = vector<vector<vector<T>>>;

template <typename T, typename Compare = std::less<T>>
using oset = tree<T, null_type, Compare, rb_tree_tag,
                  tree_order_statistics_node_update>;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt = 1;

void solve() {
    ll n, k,
        mg = 0, mn = INF,
        flag = 1; // mg-全局差分数组gcd  mn-全局最小值  flag-是否需要特判
    cin >> n >> k;
    vector<ll> v(n + 1);
    for (ll i = 1; i <= n; i++) {
        cin >> v[i];
        if (i > 1 && v[i] != v[i - 1])
            flag = 0;
        mn = min(mn, v[i]);
    }

    if (flag) { // 特判 输出 1 到 k 求和
        cout << k << ' ' << k * (k + 1) / 2 << endl;
        return;
    }

    vector<ll> ls(n + 1), rs(n + 1);      // 笛卡尔树-左右儿子
    v2ct<ll> g(22, vector<ll>(n + 1, 0)); // 差分数组+ST表

    for (ll i = 2; i <= n; i++) { // 初始化ST表第一层 + 求全局差分数组gcd
        g[0][i] = abs(v[i] - v[i - 1]);
        mg = __gcd(mg, abs(v[i] - v[i - 1]));
    }
    for (ll i = 1; i <= 20; i++) // 构建ST表
        for (ll j = 1; j <= n; j++)
            g[i][j] =
                __gcd(g[i - 1][j], g[i - 1][min(n, j + (1 << (i - 1)))]);

    function<ll(ll, ll)> Gcd = [&](ll l, ll r) { // 查询区间差分数组的gcd
        ll res = 0, _lg = abs(__lg(r - l));
        if (l < r)
            res = __gcd(g[_lg][l + 1], g[_lg][r - (1 << _lg) + 1]);
        return res;
    };

    vector<ll> ans;
    for (ll i = 1; i * i <= mg; i++) // 生成最初的答案序列
        if (mg % i == 0) {
            if (i >= mn + 1 && i <= mn + k)
                ans.emplace_back(i - mn);
            if (mg != i * i && mg / i >= mn + 1 && mg / i <= mn + k)
                ans.emplace_back(mg / i - mn);
        }

    stack<ll> stk;
    for (ll i = 1; i <= n; i++) { // 笛卡尔树建树
        ll tmp = stk.size(), lst = 0;
        while (stk.size() && v[stk.top()] > v[i])
            lst = stk.top(), stk.pop();
        if (stk.size())
            rs[stk.top()] = i;
        if (stk.size() < tmp)
            ls[i] = lst;
        stk.push(i);
    }

    function<void(ll, ll, ll)> DFS =
        [&](ll x, ll l,
            ll r) { // 逐层检验 （当前最小值下标，左端点，右端点）
            if (l == r)
                return;
            ll rgcd = Gcd(l, r); // 区间差分数组gcd

            for (ll i = 0; i < ans.size(); i++)
                if (ans[i] &&
                    rgcd % (ans[i] + v[x]) !=
                        0) // 被排除的答案设为 0
                           // （这一步可以用链表进一步优化时间，但是懒得改了）
                    ans[i] = 0;

            if (ls[x])
                DFS(ls[x], l, x - 1);
            if (rs[x])
                DFS(rs[x], x + 1, r);
        };

    vector<ll> vis(n + 1);
    ll rt; // 笛卡尔树的树根
    for (ll i = 1; i <= n; i++) {
        vis[ls[i]] = 1;
        vis[rs[i]] = 1;
    }
    for (ll i = 1; i <= n; i++)
        if (!vis[i])
            rt = i; // 没有被访问到的就是树根

    DFS(rt, 1, n); // 开始筛选答案
    ll cnt = 0, sum = 0;
    for (ll i = 0; i < ans.size(); i++) { // 计数 & 求和
        if (ans[i]) {
            cnt++;
            sum += ans[i];
        }
    }
    //	OOO
    cout << cnt << ' ' << sum << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> tt; // 非多组测试数据时注释掉即可

    while (tt--) {
        solve();
    }

    cout.flush();
    return 0;
}