AcWing5203 数学作业题解

题意：

你的数学老师布置了一项作业。

给定一个整数 \(N\) ，请你构造一个长度为 \(N\) 的整数序列 \(A_1,A_2, \ldots, A_N\) ，其中 \(1 \leq A_i \leq 10^9\) 。

构造序列需要同时满足 \(M\) 个要求，其中第 \(i\) 个要求是构造序列的连续子序列 \(A_{X_i}, \cdots, A_{Y_i}\left(1 \leq X_i \leq Y_i \leq N\right)\) 的最大公约数必须恰好等于 \(Z_i\) 。

请你输出一个满足所有要求的有效序列。

输入格式：

第一行包含两个整数 \(N, M\) 。

接下来 \(M\) 行，每行包含三个整数 \(X_i, Y_i, Z_i\) 。

输出格式：

如果满足所有要求的有效序列不存在，则输出 Impossible。

如果满足所有要求的有效序列存在，则在一行内输出该序列。

如果方案不唯一，输出任意合理方案均可。

数据范围：

\(1 \leq N, M \leq 1.5 \times 10^5,~1 \leq X_i \leq Y_i \leq N,~1 \leq Z_i \leq 16\) 。

还是尝试写一下思考过程吧。

不妨考虑每个构造要求能告诉我们什么信息。

注意到 \(Z_i \le 16\) ，因此我们可以记录每个点到底有哪些取值要求。

那么，如果我们知道一个点上有哪些要求，怎样才能满足它们呢？

答案是：填上这些要求的最小公倍数。

至此，我们已经可以构造出一个“合法”的序列了。

但是实际上，这只是每个构造要求告诉我们的部分信息，即第 \(i\) 个数一定有 \(Z_i\) 这个约数。

也就是说，我们的构造方式只能满足每个构造要求的必要条件，它的充分性无法保证。

因此我们尝试用检验的方式来找出那些不充分的构造，这就又陷入了另一个问题：

这些不充分的构造，有没有可能是因为构造方式不适用导致的（而实际上有解）？

这时候就需要用到一些所谓的直觉了。

因为做过一些有类似情况的题目，所以我们可以大胆猜测：这些情况一定无解。

于是我们尝试证明。直接硬看好像也看不出怎么证明，我们不妨从一些例子开始。

例如 \(m=2\) ，且要求为 1 3 2 和 1 5 6

可以发现这种情况是无解的，因为最大公约数不可能随着区间的扩大而增大

而我们构造的数组由于是使用最小公倍数，所以任意要求区间的最大公约数一定是不小于 \(Z_i\) 的

如果等于那就合法，如果大于 \(Z_i\) ，就一定是上面这种情况（及其等价情况）。

至此，本题做完了。检查的话用 ST 表，构造只会用到 gcd 。

时间复杂度 \(\mathcal{O}(n \log n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
typedef pair<pii,int> p3i;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
int gcd(int a,int b){ return b == 0 ? a : gcd(b, a % b); }
#define N ((int)(2e5 + 15))
#define Fi first
#define Se second

int n,m,lg[N],a[18][N],st[18][N]; p3i q[N];
int qry(int l,int r)
{ 
    int k = lg[r - l + 1];
    return gcd(st[k][l], st[k][r - (1 << k) + 1]);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> q[i].Fi.Fi >> q[i].Fi.Se >> q[i].Se;
        int x = q[i].Fi.Fi, y = q[i].Fi.Se, z = q[i].Se;
        ++a[z][x]; --a[z][y + 1]; 
    }
    for(int j = 1; j <= 16; j++)
        for(int i = 1; i <= n; i++) a[j][i] += a[j][i - 1];

    for(int i = 1; i <= n; i++)
    {
        int x = 1, y = 0;
        for(int j = 1; j <= 16; j++)
        {
            if(!a[j][i]) continue;
            x = x ? (x * j / gcd(x, j)) : j; y = max(y, j);
        }
        st[0][i] = x;
    }
    for(int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for(int j = 0; 1 << (j + 1) <= n; j++)
    {
        int *f = st[j], *g = st[j + 1];
        for(int i = 1; i + (1 << j) - 1 <= n; i++)
            g[i] = gcd(f[i], f[i + (1 << j)]);
    }
    for(int i = 1; i <= m; i++)
    {
        int x = q[i].Fi.Fi, y = q[i].Fi.Se, z = q[i].Se;
        if(qry(x,y) > z) return cout << "Impossible\n", 0;
    }
    for(int i = 1; i <= n; i++) cout << st[0][i] << " \n"[i == n];
    return 0;
}