luogu2261余数求和题解--整除分块

题目链接

https://www.luogu.org/problemnew/show/P2261

分析

显然$k$ $mod$ $i=k-\lfloor {k/i}\rfloor$ $\times$ $i$,于是我们只需要求$N * k-\sum_{i=1}^N {\lfloor {k/i}\rfloor\times i}$

这里就需要数论分块,也称作整除分块的知识

结论:

$\forall{i} \in [x,\lfloor {k/{\lfloor {k/x}\rfloor }}\rfloor]$,$\lfloor k/i \rfloor$的值都相等

证明

先咕了….

于是这道题再套个等差数列求和就完了…

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#define ll long long 
#define ri register int 
using std::min;
using std::max;
ll n,k,ans=0,g;
int main(){
	scanf("%lld %lld",&n,&k);
	ans=n*k;
	for(ri i=1;i<=n;i=g+1){
		g= k/i ? min(k/(k/i),n) : n;//如果i大于k的话直接一步把后面的算完 
		ans -= (i+g)*(g-i+1)/2 * (k/i);	
		//     等差数列求和      数论分块 
	}
	printf("%lld\n",ans);
	return 0;
}