AT_ABC230_E题解
中缀自动机
·
·
题解
基础：
-
求和符号
-
\sum\limits_{i=1}^na_i=a_1+a_2+...+a_n
-
向下取整：
-
\left\lfloor\dfrac{1}{2}\right\rfloor=0,\left\lfloor-\dfrac{1}{2}\right\rfloor=-1
-
向上取整：
-
\left\lceil\dfrac{1}{2}\right\rceil=1,\left\lceil-\dfrac{1}{2}\right\rceil=0
正题：
当有一个这样的问题：
\sum\limits_{i=1}^{10}{\left\lfloor\tfrac{10}{i}\right\rfloor}=?
列个表格?
\boxed{\left\lfloor\dfrac{10}{1}\right\rfloor=10},\boxed{\left\lfloor\dfrac{10}{2}\right\rfloor=5},\boxed{\left\lfloor\dfrac{10}{3}\right\rfloor=3},\boxed{\left\lfloor\dfrac{10}{4}\right\rfloor=2},\boxed{\left\lfloor\dfrac{10}{5}\right\rfloor=2},
\boxed{\left\lfloor\dfrac{10}{6}\right\rfloor=1},\boxed{\left\lfloor\dfrac{10}{7}\right\rfloor=1},\boxed{\left\lfloor\dfrac{10}{8}\right\rfloor=1},\boxed{\left\lfloor\dfrac{10}{9}\right\rfloor=1},\boxed{\left\lfloor\dfrac{10}{10}\right\rfloor=1}
如果我们把这些一个一个加起来，那会很慢，那么怎么办呢？
于是，观察表格可以发现，有一些答案和后面的答案一样（一段区间内一样）
那么我们就可以把 1\sim 10 分个段：分别是 1,2,3,4\sim 5,6\sim 10
这样我们就只用计算 5 次 \left\lfloor\dfrac{10}{i}\right\rfloor就行了。
那么，问题来了，如何确定答案相同的区间呢？
公式推导：
\sum\limits_{i=1}^{n}{\left\lfloor\tfrac{n}{i}\right\rfloor}=?
（注：n 为正整数）
假设我们已知某一个分块的左端点 l，要求解出该分块的右端点 r。设该分块的数值为 k，对于该分块中的每个数 i，有 k=\left\lfloor\dfrac{n}{i}\right\rfloor=\left\lfloor\dfrac{n}{l}\right\rfloor，即 ik\leq n，想一想就可以知道当 i=r 时，也就是 \max(rk)\leq n 为最大值。
所以，就可以发现：
r=\left\lfloor\dfrac{n}{k}\right\rfloor
又因为：
k=\left\lfloor\dfrac{n}{l}\right\rfloor
所以：
r=\left\lfloor\dfrac{n}{\left\lfloor\dfrac{n}{l}\right\rfloor}\right\rfloor
则，代码如下：
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
inline void print(int x){
if(x<0)putchar('-'),x=-x;
if(x>9)print(x/10);
putchar(x%10^48);
}
int t,n;
signed main(){
n=read();
int ans=0;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
ans+=(r-l+1)*(n/l);
}
print(ans);
return 0;
}
$\left\lfloor \frac{n}{l}\right\rfloor=\left\lfloor\frac{n}{r}\right\rfloor
证：
r=\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor
证明：
\left\lfloor\frac{n}{l}\right\rfloor\leq\frac{n}{l}
l=\left\lfloor\frac{n}{\frac{n}{l}}\right\rfloor \leq \left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor
l_{\max}=\left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor=r
证毕。