# bzoj 4028 [HEOI2015]公约数数列

### Description

1. MODIFY id x: 将 $a_{id}$ 修改为 x.
2. 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表示最大公约数。

### Output

#### 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

6

0

no

2

8

8

### 题解

#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");
}
}
}