抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

HEOI2015 公约数数列

This is a picture without description

pufanyi

题解

发布于：Mar 10, 2019

设计一个数据结构. 给定一个正整数数列a0,a1,...,an−1a_0, a_1, ..., a_{n - 1}，你需要支持以下两种操作：

  1. MODIFY id x：将 aida_{id} 修改为xx。
  2. QUERY x：求最小的整数p(0≤p<n)p (0 \le p < n)，使得gcd⁡i=0pai×⨂i=0pai=x\gcd_{i=0}^pa_i\times \bigotimes_{i=0}^p a_i= x。无解输出no。

n≤100000n \le 100000，q≤10000q \le 10000，ai≤109(0≤i<n)a_i \le 10^9 (0 \le i < n)，QUERY x 中的 x≤1018x \le 10^{18}，MODIFY id x 中的 0≤id<n0 \le id < n，1≤x≤1091 \le x \le 10^9。

题解

前缀 gcd⁡\gcd 序列有一个有趣的性质，那就是后一个数一定是前一个数的因数，所以至少会除22。

于是我们发现前缀 gcd⁡\gcd 序列之多只会有 log⁡\log 个不同的数。

考虑到 gcd⁡\gcd 与⨂\bigotimes没有什么太大的联系，我们考虑枚举gcd⁡\gcd，然后找出⨂i=0pai=xgcd⁡i=0pai\bigotimes_{i=0}^p a_i=\frac{x}{\gcd_{i=0}^pa_i}。

发现仍然很难维护，于是我们考虑分块。

对于每个块维护块内最后一个元素的前缀gcd⁡\gcd，块内gcd⁡\gcd，以及每个元素的前缀异或和。

首先是修改异或和。修改单点后，要将后面所有的 xor\text{xor} 值全部修改。直接对每个块打一个标记即可。

修改 gcd⁡\gcd 也很方便，块内 gcd⁡\gcd 与前缀 gcd⁡\gcd 均可暴力维护。

查询某块时，如果其第一个数的前缀 gcd⁡\gcd（上一个块最后一个数的前缀gcd⁡\gcd 与这一个块的第一个数的 gcd⁡\gcd）与其最后一个数的前缀gcd⁡\gcd 不相等，直接暴力修改。由于前缀 gcd⁡\gcd 序列只有 log⁡\log 个不同的数。单次复杂度是O(nlog⁡n)\mathcal{O}(\sqrt n\log n)。

如果相等，那也就意味着块内所有数的前缀 gcd⁡\gcd 均相等。只要查询前缀 xor\text{xor} 即可。对每个块开一个 map/hash 查一下就可以了。单次操作复杂度O(nlog⁡n)\mathcal{O}(\sqrt n\log n)。

所以总复杂度是O(qnlog⁡n)\mathcal{O}(q\sqrt n\log n)，需要卡常。

博主太菜 luogu 过了 bzoj 没卡过去，假装过了的样子。

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <cstdio>
#include <cmath>
#include <map>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 100005;

typedef long long LL;

template <class T>
inline void writeln(T x)
{
    if(!x)
    {
        puts("0");
        return;
    }
    if(x < 0)
    {
        putchar('-');
        x = -x;
    }
    int bit[20] = {0};
    while(x)
    {
        bit[++(*bit)] = (x % 10) | 48;
        x /= 10;
    }
    do
        putchar(bit[*bit]);
    while(--(*bit));
    puts("");
}

inline int gcd(int a, int b)
{
    int t;
    while (b)
    {
        t = a % b;
        a = b;
        b = t;
    }
    return a;
}

int n;
int kc, ds;

int hgcd[maxn]; // 块后的前缀 gcd
int kgcd[maxn]; // 块内 gcd
int belong[maxn];
int ll[maxn], rr[maxn];
map<int, int> mp[maxn];
int yuan[maxn];
int qz_xor[maxn];
int lzy_xor[maxn];

inline void modify(int id, int x)
{
    int tx = x;

    // 先改 xor
    x ^= yuan[id];
    for (register int i = id; i <= rr[belong[id]]; ++i)
        qz_xor[i] ^= x;
    mp[belong[id]].clear();
    for (register int i = ll[belong[id]]; i <= rr[belong[id]]; ++i)
    {
        qz_xor[i] ^= lzy_xor[belong[i]];
        if (!mp[belong[id]][qz_xor[i]])
            mp[belong[id]][qz_xor[i]] = i;
    }
    lzy_xor[belong[id]] = 0;
    if (rr[belong[id]] != n)
        for (register int i = belong[id] + 1; i <= ds; ++i)
            lzy_xor[i] ^= x;

    // 然后是 gcd
    yuan[id] = tx;
    kgcd[belong[id]] = 0;
    for (register int i = ll[belong[id]]; i <= rr[belong[id]]; ++i)
        kgcd[belong[id]] = gcd(kgcd[belong[id]], yuan[i]);
    for (register int i = belong[id]; i <= ds; ++i)
    {
        int tmp = gcd(hgcd[i - 1], kgcd[i]);
        if (tmp == hgcd[i])
            break;
        else
            hgcd[i] = tmp;
    }
}

inline int query(LL x)
{
    for (int i = 1; i <= ds; ++i)
    {
        if (!(x % (LL) hgcd[i]))
        {
            int qiangcd = gcd(hgcd[i - 1], yuan[i]);
            if (qiangcd != hgcd[i])
            {
                for(int j = ll[i], nowg = hgcd[i - 1]; j <= rr[i]; ++j)
                {
                    nowg = gcd(nowg, yuan[j]);
                    if(nowg * (LL) (qz_xor[j] ^ lzy_xor[i]) == x)
                        return j;
                }
            }
            else
            {
                LL xx = (x / (LL) hgcd[i]) ^ lzy_xor[i];
                if(mp[i][xx])
                    return mp[i][xx];
            }
        }
    }
    return -1;
}

inline void pre()
{
    scanf("%d", &n);
    kc = sqrt(n);
    ds = n / kc;
    if (n % kc)
        ds++;
    for (int i = 1; i <= ds; ++i)
    {
        ll[i] = rr[i - 1] + 1;
        rr[i] = min(ll[i] + kc - 1, n);
        for (int j = ll[i]; j <= rr[i]; ++j)
        {
            scanf("%d", &yuan[j]);
            kgcd[i] = gcd(yuan[j], kgcd[i]);
            qz_xor[j] = qz_xor[j - 1] ^ yuan[j];
            if (!mp[i][qz_xor[j]])
                mp[i][qz_xor[j]] = j;
            belong[j] = i;
            hgcd[i] = gcd(hgcd[i - 1], kgcd[i]);
        }
    }
}

int main()
{
    pre();
    char s[233];
    int Q;
    scanf("%d", &Q);
    while(Q--)
    {
        scanf("%s", s);
        if(s[0] == 'M')
        {
            int id, x;
            scanf("%d%d", &id, &x);
            modify(id + 1, x);
        }
        else
        {
            LL x;
            scanf("%lld", &x);
            int ans = query(x);
            if(~ans)
                writeln(ans - 1);
            else
                puts("no");
        }
    }
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://pufanyi.github.io/oi-blog/[HEOI2015]%E5%85%AC%E7%BA%A6%E6%95%B0%E6%95%B0%E5%88%97/

更新于：Jul 2, 2023

数据结构

分块

卡常

评论