比赛链接

AC 5题，Rank 26th

题意:

裸的FWT

题解:

generator和amplifier注意差分预处理,然后FWT得到receiver

最后预处理前缀和即可回答每组询问

by Hardict

题意:

给定$\{a_{i}\}_{i=1}^{n}$,多组询问$(l,r,x)$,求$\sum_{i=l}^{r}[gcd(a_{i},x)==1]$,强制在线

题解:

可以转变为求解$[1,r]$中满足的个数

考虑一个经典问题$1-n中与m互素的数的个数$,可以理题容斥解决

回到该题,可以知道判断素因子即可而且容斥利用的是$\mu(d)\neq 0$的数,针对多组询问,先预处理$1-1e5$每个数的约数中$\mu(d)\neq 0的d$

设$f[r][d]表示a_{1}\sim a_{r}中,\{i:d|a_{i}\}的集合大小$,即可针对每个询问,进行不超过约数个数$\sigma_{0}(x)\leq 128$次容斥即可

但$f[r][d]$实际转移量过大,注意到针对每个$d$,$f[r][d]$每次大小改变的$r$位置可知,且针对每个$a_{r}$,至多有$\sigma_{0}(a_{r})$个$d$改变

针对每个$d$存储改变位置,查询时利用$upper_bound$即可得到对应的$f[r][d]$值,即可完成计算

时间复杂度为:全局预处理$O(1e5 log1e5)$,每组预处理$O(n\sigma_{0}(a_{i}))$,单次询问$O(\sigma_{0}(x)\sigma_{0}(a_{i}))$