首页 > 题解 > bzoj 4028 [HEOI2015]公约数数列

bzoj 4028 [HEOI2015]公约数数列

Description

设计一个数据结构. 给定一个正整数数列 $a_0, a_1, …, a_{n – 1}$,你需要支持以下两种操作:

  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表示最大公约数。

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变化了,就直接暴力这一块


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×