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\)的值都相等

证明

先咕了....

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

代码

#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;

}

巴特西

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

题目链接

分析

结论:

证明

代码

最新文章

热门文章