整除分块

佚名 6年前 (2019-04-24) 随笔 1730人围观抢沙发百度已收录

$O(\sqrt{a_i})$求所有$f(\lfloor\frac{a_1}{d}\rfloor,\lfloor\frac{a_2}{d}\rfloor,...)$的值, 因为$j=\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$是最大的$j$, 使得$\lfloor\frac{n}{i}\rfloor=\lfloor\frac{n}{j}\rfloor$

    scanf("%d", &n);
    REP(i,1,n) scanf("%d", a+i);
    int mx = *max_element(a+1,a+1+n);
    for (int i=1,j; i<=mx; i=j+1) {
        j = 1e9;
        REP(k,1,n) if (a[k]/i) j=min(j,a[k]/(a[k]/i));
        //现在 a[1]/i,a[1]/(i+1),...,a[1]/j相等
        //a[2]/i,a[2]/(i+1),...,a[2]/j相等
        //...
    }

上取整分块从大到小即可, 是因为$j=\lceil\frac{n}{\lceil\frac{n}{i}\rceil}\rceil$是最小的$j$, 使得$\lceil\frac{n}{i}\rceil=\lceil\frac{n}{j}\rceil$

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

    scanf("%d", &n);
    REP(i,1,n) scanf("%d", a+i);
    int mx = *max_element(a+1,a+1+n);
    for (int i=mx,j; i; i=j-1) {
        j = 0;
        REP(k,1,n) if (Div(a[k],i)) j=max(j,Div(a[k],Div(a[k],i)));
    }