首页 > 代码库 > gcd的性质+分块 Bzoj 4028
gcd的性质+分块 Bzoj 4028
4028: [HEOI2015]公约数数列
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 865 Solved: 311
[Submit][Status][Discuss]
Description
设计一个数据结构. 给定一个正整数数列 a_0, a_1, ..., a_{n - 1},你需要支持以下两种操作:
Input
输入数据的第一行包含一个正整数 n.
Output
对于每个 QUERY 询问,在单独的一行中输出结果。如果不存在这样的 p,输出 no.
Sample Input
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
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每次必然是/2的,所以gcd最多就只要log个,然后呢,我们对每个块都分块,并且记录每个块的gcd[i]和xor[i],分别表示gcd(1~i)和xor(1~i),
①如果是单点修改的话,就暴力更新一下目前的块即可,所以暴力更新的复杂度为n^0.5
②如说是查询的话,我们就暴力每个块,对于目前这个块。
定义pregcd表示目前这个块之前所有的数字的gcd,prexor为目前这个块之前所有的数字的xor。然后,如果这个块中,他的gcd[r[i]]和pregcd求gcd以后没有发生变化,那么就表示可能存在xor[j]^prexor * (pregcd和gcd[r[i]]的gcd) = val。那么我们就二分去看看存不存在这个xor[j],如果存在,就从头开始暴力,找到最小的。当然,这个二分的话可以用set来维护,只需要set.count()就可以查询了。所以这里的复杂度为sqrt(n) * log(sqrt(n))
如果gcd发生了变化那么我们就暴力去查询即可,所以这里的复杂度为sqrt(n).
因为gcd最多不会超过log个,所以上面查询+修改的最大复杂度为q*sqrt(n)*log(sqrt(n))
//看看会不会爆int!数组会不会少了一维! //取物问题一定要小心先手胜利的条件 #include <bits/stdc++.h> using namespace std; #pragma comment(linker,"/STACK:102400000,102400000") #define LL long long #define ALL(a) a.begin(), a.end() #define pb push_back #define mk make_pair #define fi first #define se second #define haha printf("haha\n") /* 首先,我们对所有的东西进行分块,然后我们对每个区间进行处理,分别得到这个区间的gcd和xor。 ①然后如果前面的区间到这个块以后的gcd如果发生了改变,那么,我们就暴力这个块,复杂度为sqrt(n) ②如果前面的区间到这个块以后gcd没有发生改变,那么我们就二分这个块,二分的证明如下: 假定lastxor是该区间之前的xor值,lastgcd是该区间之前的gcd的值,假定我们要寻找的xor[j]是在这个块中 那么xor[j]^lastxor * lastgcd = k,转化以后为xor[j] = k/lastgcd ^ lastxor,所以我们只要二分这个块就好了 因此这里的复杂度为logn 因为gcd一共就只有logn个,所以复杂度最坏为sqrt(n) * logn个 */ const int maxn = 1e6 + 5; LL a[maxn], Xor[maxn], gcd[maxn]; int l[maxn], r[maxn], block, num, belong[maxn]; int n, q; set<LL> S[maxn]; LL get_gcd(LL a, LL b){ return b == 0 ? a : get_gcd(b, a % b); } void build(){ block = sqrt(n); 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++){ belong[i] = (i - 1) / block + 1; } } void update(int p){ S[p].clear(); gcd[l[p]] = a[l[p]], Xor[l[p]] = a[l[p]]; S[p].insert(Xor[l[p]]); for (int i = l[p] + 1; i <= r[p]; i++){ gcd[i] = get_gcd(gcd[i - 1], a[i]); Xor[i] = Xor[i - 1] ^ a[i]; S[p].insert(Xor[i]); } } void query(LL val){ LL prexor, pregcd; for (int i = 1; i <= r[1]; i++){ if (gcd[i] * Xor[i] == val){ printf("%d\n", i-1); return ; } } prexor = Xor[r[1]], pregcd = gcd[r[1]]; for (int i = 2; i <= num; i++){ LL nowgcd = get_gcd(pregcd, gcd[r[i]]); if (nowgcd == pregcd){///xor[i] ^ prexor * nowgcd = val LL tmp = val / nowgcd ^ prexor; if (val % nowgcd == 0 && S[i].count(tmp)){ for (int j = l[i]; j <= r[i]; j++){ if (Xor[j] == tmp){ printf("%d\n", j - 1); return ; } } } } else { for (int j = l[i]; j <= r[i]; j++){ nowgcd = get_gcd(gcd[j], pregcd); LL tmp = val / nowgcd ^ prexor; if (val % nowgcd == 0 && Xor[j] == tmp){ printf("%d\n", j - 1); return; } } } pregcd = get_gcd(pregcd, gcd[r[i]]); prexor = prexor ^ Xor[r[i]]; } printf("no\n"); } int main(){ cin >> n; for (int i = 1; i <= n; i++){ scanf("%lld", a + i); } build(); for (int i = 1; i <= num; i++) update(i); scanf("%d", &q); char ch[20]; for (int i = 1; i <= q; i++){ scanf("%s", ch); if (ch[0] == ‘M‘){ int p; LL val; scanf("%d%lld", &p, &val); a[++p] = val; update(belong[p]); } else{ LL val; scanf("%lld", &val); query(val); } } return 0; }
gcd的性质+分块 Bzoj 4028