题目大意

给出正整数 n 和 k 计算 \(G(n, k)=k\ \bmod\ 1 + k\ \bmod\ 2 + k\ \bmod\ 3 + \cdots + k\ \bmod\ n\) 的值 其中 \(k\ \bmod\ i\) 表示 k 除以 i 的余数。

解析

整除分块的一个典型例子。

整除分块解决的是形如

的问题，其复杂度为\(O(\sqrt{n})\)。

实际上是规律性的一类问题，打表可以发现对于一些连续的\(i\)，\(\lfloor\frac{n}{i}\rfloor\)具有相同的值。具体而言，对于一个\(i\)，在一个区间\(i\sim \lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor\)中，\(\lfloor\frac{n}{i}\rfloor\)具有相同的值。

也就是说，对于这个问题，我们只需要把整除分块中每一块的和累加就行了。

回到这道题，把题意转化为数学语言

根据模算术的定义，可以写成

即

后面的东西就是整除分块，对于一个块\(l\sim r\)，有

所以对于一个块，\(\sum_{i=l}^r ~ i\) 实际上是一个等差数列，我们一并求出来就可以了。

参考代码

#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<ctime>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#define ll long long

using namespace std;

ll n,k;

int main()

{

	scanf("%d%d",&n,&k);

	ll tmp=0;

	for(int l=1,r=0;l<=n;l=r+1){

		if(!(k/l)) r=n;

		else r=min(k/(k/l),n);

		tmp+=(r-l+1)*(k/l)*(l+r)/2;

	}

	printf("%lld\n",n*k-tmp);

	return 0;

}