[补题]2017多校D-BD-区间筛/二分+线段树

2017多校4-BD-区间筛/二分+线段树

继续单刷,场内过了BIK三题,D题本来应该也要能做的(但是读错题意了…)

B题:http://acm.hdu.edu.cn/showproblem.php?pid=6069,(d(k))表示(k)的约数的个数,求(sum_{i=l}^{r}d(i^k))取模的值,(l,rleq 1e12,r-lleq 10^6)

对质数(p)(d(p^k)=k+1),同时如果(mot n),容易得到(d(mn)=d(n)d(m))(因为如果(t|m)(t ot |n)),所以最暴力的就是对每个(i)质因数分解(i=p_1^{q_1}p_2^{q_2}dots,p_t^{q_t})(d(i^k))就是(prod_{i}^t(kq_i+1)),但是暴力对区间内每个数分解会炸,昨天组队的时候傻逼写了个Pollard-Rho也没过(x)

后来去装了个水想到的,正着做不行,就考虑每个素数的影响,(10^6)内的素数大约有(frac{10^6}{ln 10^6}approx 7 imes 10^4)个,用每个素数(p)的倍数去“筛”([l,r])里的数字,具体来说就是枚举每个(p_i),一开始设一个(x=lfloorfrac{l}{p_i} floor p_i),如果(x)落在([l,r])内就去算这个(x)有多少个(p_i),最后给(x)加上(p_i),直到(x)超过(r)

这样子总的复杂度就是(sum_{pin P} frac{r-l}{p}),其中(P)(1)(10^6)内所有质数的集合,分母求和就是一段区间内素数倒数求和,这篇博客:https://www.cnblogs.com/yoshinow2001/p/14610848.html里给出了它是(O(ln ln n))的复杂度。

void upd(ll &x,ll t){x=(x*(t*k+1))%MOD;}

for(ll i=l;i<=r;++i)Q[i-l]=1,x[i-l]=i;
rep(i,1,cnt){
    if(pri[i]>r)break;
    ll p=l/pri[i]*pri[i];
    while(p<=r){
        if(l<=p&&p<=r){
            ll t=0;
            while(x[p-l]%pri[i]==0){
                x[p-l]/=pri[i];
                t++;
            }
            upd(Q[p-l],t);
        }
        p+=pri[i];
    }
}
for(ll i=l;i<=r;++i)if(x[i-l]>1)upd(Q[i-l],1);

D题:给一个序列,求(egin{aligned}frac{cnt[l,r]}{r-l+1}end{aligned})的最小值,(nleq 6 imes 10^4)

一开始读错题意了,GG,读对题意后会想到一个叫做01分数规划的东西,考虑二分,对于当前的一个(m),固定一个端点,比如说是(r),就只要check是否存在(l:cnt[l,r]-mlleq m(r+1)),也就是找(cnt[l,r]-ml)的最小值,如果对每个(r)都暴力查一遍复杂度肯定炸了,但每次查询的区间([1,1],[1,2],dots,[1,n])是逐渐变大的,我们就考虑一边修改一边查询前缀的最小值,每次(l+1)相当于在(l)这个位置加上一个(-ml),cnt的影响则是一整段区间:我们新加了一个数(a_i),他会对([last[a_i]+1,i])的部分的cnt有1的贡献,于是这是一个区间加,就用线段树解决啦。

代码:https://paste.ubuntu.com/p/Fjs3jkg5RJ/

原文地址:https://www.cnblogs.com/yoshinow2001/p/14651082.html