bzoj 4028 [HEOI2015]公约数数列
内容
Description
设计一个数据结构. 给定一个正整数数列 $a_0, a_1, …, a_{n – 1}$，你需要支持以下两种操作：
- MODIFY id x: 将 $a_{id}$ 修改为 x.
- QUERY x: 求最小的整数 p (0 <= p < n)，使得 $gcd(a_0, a_1, …, a_p) * XOR(a_0, a_1, …, a_p) = x$. 其中 $XOR(a_0, a_1, …, a_p)$ 代表 $a_0, a_1, …, a_p$ 的异或和，gcd表示最大公约数。
Input
输入数据的第一行包含一个正整数 n.
接下来一行包含 n 个正整数 $a_0, a_1, …, a_{n – 1}$.
之后一行包含一个正整数 q，表示询问的个数。
之后 q 行，每行包含一个询问。格式如题目中所述。
Output
对于每个 QUERY 询问，在单独的一行中输出结果。如果不存在这样的 p，输出 no.
Sample Input
10
1353600 5821200 10752000 1670400 3729600 6844320 12544000 117600 59400 640
10
MODIFY 7 20321280
QUERY 162343680
QUERY 1832232960000
MODIFY 0 92160
QUERY 1234567
QUERY 3989856000
QUERY 833018560
MODIFY 3 8600
MODIFY 5 5306112
QUERY 148900352
Sample Output
6
0
no
2
8
8
HINT
对于 100% 的数据，n <= 100000，q <= 10000，a_i <= 10^9 (0 <= i < n)，QUERY x 中的 x <= 10^18，MODIFY id x 中的 0 <= id < n，1 <= x <= 10^9.
题解
根据前缀GCD，肯定GCD在不断的减小的，而且每次减小最少都是除以2的
所以前缀gcd的种类最多logn种
于是我们就分块搞
那hash表把每一块的xor都存下来
如果这一块内的gcd不变的话，我就直接拿这一块的hash表去查询就好了
如果gcd变化了，就直接暴力这一块
|
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 |
#include <cstdio> #include <algorithm> #include <set> #include <cmath> using namespace std; const int N = 100010; int a[N], l[N], r[N], bl[N], gd[N], xr[N], block, num, n, T, y; long long x; char st[10]; set<int> s[100]; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } void build(int t) { s[t].clear(); gd[l[t]] = a[l[t]], xr[l[t]] = a[l[t]]; s[t].insert(xr[l[t]]); for (int i = l[t] + 1; i <= r[t]; ++i) gd[i] = gcd(gd[i - 1], a[i]), xr[i] = xr[i - 1] ^ a[i], s[t].insert(xr[i]); } void init() { block = (int)sqrt(n + 0.5); num = n / block; if (n % block) num++; for (int i = 1; i <= num; ++i) l[i] = (i - 1)* block + 1, r[i] = i * block; r[num] = n; for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / block + 1; for (int i = 1; i <= num; ++i) build(i); } main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); init(); scanf("%d", &T); while (T--) { scanf("%s", st); if (st[0] == 'M') scanf("%lld%d", &x, &y), x++, a[x] = y, build(bl[x]); else { scanf("%lld", &x); int flag = 0, lg = 0, lx = 0; for (int i = 1; i <= num; ++i) { int tmp = gcd(lg, gd[r[i]]); if (tmp != lg) { for (int j = l[i]; j <= r[i]; ++j) if (1ll * (xr[j] ^ lx) * (gcd(lg, gd[j])) == x) { flag = j; break; } if (flag) break; } else if (x % tmp == 0 && s[i].count((int)(x / tmp) ^ lx)) { for (int j = l[i]; j <= r[i]; ++j) if (1ll * (xr[j] ^ lx) * (gcd(lg, gd[j])) == x) { flag = j; break; } if (flag) break; } lg = tmp, lx ^= xr[r[i]]; } if (flag) printf("%d\n", flag - 1); else puts("no"); } } } |