整除分块

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

    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=lceilfrac{n}{lceilfrac{n}{i} ceil} ceil$是最小的$j$, 使得$lceilfrac{n}{i} ceil=lceilfrac{n}{j} ceil$

    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)));
    }