UVA11526【模板】整除分块

· · 题解

写在前面

整除分块其实是运用一段连续的序列在题目所给定的式子中所给出来的一些性质，将它分为一个一个的块进行集中处理，从而减少时间开销

思路

首先，可以看出是贡献值是向下取整的，很容易想到一个性质，假设当前枚举到 x ，那么一定会存在一个最大的 y，使得：

\lfloor\frac{n}{x}\rfloor=\lfloor\frac{n}{x+1}\rfloor=\lfloor\frac{n}{x+2}\rfloor+…+\lfloor\frac{n}{y}\rfloor \ \ \text{成立}

那么考虑一下用不等式找出 y 的最大值来。

\lfloor \frac{n}{x}\rfloor\leq \frac{n}{y} y\leq\lfloor \frac{n}{\lfloor\frac{n}{x}\rfloor}\rfloor

由此得出：

y_{max}=\lfloor\frac{n}{\lfloor\frac{n}{x}\rfloor}\rfloor

那么这一段的贡献值为：

(y-x+1)\times \lfloor \frac{n}{x}\rfloor

考虑到 n 是可能包含在最后一段符合这个性质的块中的位置，去一个 \operatorname{min} 即可。

代码实现

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
#define int long long 
using namespace std;
int T;
int read()
{
    int f=1,x=0;
    char s=getchar();
    while(s<'0'||s>'9')
    {
        if(s=='-')
            f=-1;
        s=getchar();
    }
    while(s>='0'&&s<='9')
    {
        x=(x<<1)+(x<<3)+(s^'0');
        s=getchar(); 
    }
    return f*x;
}
int H(int n)
{
    // floor (n/l) <= n/r
    // r <=n/floor(n/l)
    int ans=0;
    int j;
    for(int i=1;i<=n;i=j+1)
    {
        j=n/(n/i);
        ans+=(min(j,n)-i+1)*(n/i);
    }
    return ans;
}
signed main()
{
    T=read();
    while(T--)
    {
        int opt=read();
        printf("%lld\n",H(opt));
    }
    return 0;
}