求$\sum_{i=1}^{n} \left \lfloor \frac{n}{i} \right \rfloor $

可用暴力枚举 时间复杂度o(n)

1
2
3
4
5
6

int ans = 0;
int n ;
std::cin>>n;
for(int i = 1;i<=n;++i){
	ans+=n/i;
}

通过以下代码不难发现 在一定范围内整数是成块状 也就是在一定范围内是相等的

1

for(int i = 1;i<=100;++i) std::cout<<100/i<<" ";

我们只需要找到每次块的最右边的端点 就可以通过(r-l+1) * (n/i)找到答案 时间复杂度为$O(\sqrt{n})$

$n=\sqrt{n}*\sqrt{n}$

$\frac{n}{i}$ , 若 $i > \sqrt{n} $ 则 有$[\sqrt{n} + 1 , n]$ 差不 $\sqrt{n}$种可能

若 $i <= \sqrt{n} $ 则 可除得$ [1,\sqrt{n}]$ 也是差不多$\sqrt{n}$种可能

那么总共$2\sqrt{n}$种可能 总的时间复杂度$O(\sqrt{n})$

问题是怎么找到每个块的最右端点 ， 始终是i 相当于是找 $i<=i_{max}$ 首先

寻找 i , k , n 三者之间的关系 之后消掉$k$ 变为 $n$与$i$的 关系

$i$所在块的值$ k = \left \lfloor \frac{n}{i} \right \rfloor $ 去掉下取整 $ k <= \frac{n}{i}$ 向$i<=i_{max}$靠近 $i<=\frac{n}{k}$ 把$k$带入 $i<= \frac{n}{ \left \lfloor \frac{n}{i} \right \rfloor }$

同时向下取整

∵ $i_{max}∈Z^{+}$ $\left \lfloor i_{max} \right \rfloor $ = $i_{max}$

$\left \lfloor i_{max} \right \rfloor = \left \lfloor\frac{n}{ \left \lfloor \frac{n}{i} \right \rfloor } \right \rfloor >= i$

方法2

在一个分块里存在$\left \lfloor \frac{n}{r} \right \rfloor = \left \lfloor \frac{n}{l} \right \rfloor = d$ 其中l为左端点 ， r为右端点

去掉下取整 则 $ \frac{n}{r} <=d , r <= \frac{n}{d}$ $\left \lfloor \frac{n}{l} \right \rfloor = d$

$r<=\frac{n}{\frac{n}{l}}$

∴ 每个块的最最右端点 n/(n/i)

1
2
3
4
5
6
7
8

int n ;
std::cin>>n;
for(int l = 1;i<=n;++l){
    if(n/l == 0) break; //小优化
    int r = n/(n/l); 
    //...
    l = r + 1;
}

作业： https://www.luogu.com.cn/problem/P2261

解析：

$$G(n, k) = \sum_{i = 1}^n k \bmod i$$

$ a \% b = a- a\times\left \lfloor \frac{a}{b} \right \rfloor$

$= \sum_{i = 1}^n (k- i \times \left \lfloor \frac{k}{i} \right \rfloor ) $

$= n\times k - { \sum_{i=1}^{n}}(i* \left \lfloor \frac{k}{i}\right \rfloor ) $

对于每个区块[l,r] 有

$\sum_{i=l}^{r}i\times\left \lfloor \frac{k}{i}\right \rfloor $

又因为是分块的 所以 $\left \lfloor \frac{k}{i}\right \rfloor$ 每一项都相等 既有

$\left \lfloor \frac{k}{i}\right \rfloor\sum_{i=l}^{r}i$

由等差数列公式 $n\times \frac{(a_{1}+a_{n})}{2}$ 最终就是如下形式

$n\times k - { \sum_{i=1}^{n}}\left \lfloor \frac{k}{i}\right \rfloor\sum_{i=l}^{r}i$

答案

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

void solve(){
	ll n , k;
	std::cin>>n>>k;
	ll ans = 0;
	ans = n*k;
	for(int i = 1;i<=n;++i){
		if(k / i == 0) break; //i不断增大 如果向下取整k/i == 0 后面的块都为0
		//换一种方法理解 防止后面除0异常
		//因为 i增大 k/i在减小 k/k/i在增大 
		//如果超过了n 就没必要继续枚举下去了
		int r = min(k/(k/i),n); 
		ans-=(k/i)*(r-i+1)*(i+r)/2;//等差数列
		i = r;
	}
	std::cout<<ans<<"\n";
}