题面

题意概括

定义数列 $a$，满足 $a_{k}$ 为：

对于所有 $1≤i≤k$，不同的 $\lfloor \frac{k}{i} \rfloor$ 的个数。

现希望求出 $\sum\limits_{k≡r(mod=m)}^{1≤k≤n} a_{k}$ 的值

数据范围：$1≤t≤10，0≤r<m≤n≤10^{13}$

题解

首先，这道题既然可以达到 $10^{13}$ 数量级，那么任何 $O(tn)$ 级的算法肯定都是过不去的。

那我们来看看 $a$ 这个数列。从题面中给出的前几项我们就可以猜出绝对有规律，那么打表猜一下规律：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	for(int i=1;i<=100;i++)
	{
		int ans=1;
		for(int j=2;j<=i;j++)
		{
			if(i/j!=i/(j-1)) ans++;
		}
		cout<<ans<<" ";
	}
}

打出来的表是这样的：

$1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,8,9,9,9,9,9,10,10,10,10,10,10,11,11,11,11,11,11\cdot\cdot\cdot\cdot\cdot\cdot$

相信已经可以看出来规律了。（证明略，请自行查阅关于数列分块相关论述）

用数学语言描述一下，就是对于 $p$ 最大的 $a_{p}=i$，有：

当 $i$ 为单数时，$p=(\sum\limits_{j=2}^{\frac{i+1}{2}} 2j)+1=(\frac{i+1}{2})^2+\frac{i+1}{2}-1$ ，且可以发现 $\frac{i+1}{2}=count(a_{p}=i)$

当 $i$ 为双数时同理，$p=(\sum\limits_{j=2}^{\frac{i}{2}} 2j)+1+\frac{i+2}{2}=(\frac{i+2}{2})^2-1$，且可以发现 $\frac{i+2}{2}=count(a_{p}=i)$

综上，$\lfloor\frac{i+2}{2}\rfloor=count(a_{p}=i)$ 。令 $a=count(a_{p}=i)$

根据刚才的结论，我们可以得出：

当 $i$ 为双数时，有：

$(a-1)^2+(a-1)≤p<a^2$

解方程 $(a-1)^2+(a-1)=p$，得 $a-1=\frac{\sqrt{4p+1}-1}{2}$ （负根舍去）

则 $a-1=\lfloor\frac{\lfloor\sqrt{4p+1}\rfloor-1}{2}\rfloor$，显然有 $2(a-1)≤\lfloor\sqrt{4p+1}\rfloor-1≤2a-1$

则 $2a-1≤\lfloor\sqrt{4p+1}\rfloor≤2a$，又由于 $p<a^2$ ，则 $p≤a^2-1$，则 $4p+1<4a^2$，$\lfloor\sqrt{4p+1}\rfloor<2a$，

则 $2a-1=\lfloor\sqrt{4p+1}\rfloor$，为单数，则 $\lfloor\frac{\lfloor\sqrt{4p+1}\rfloor-1}{2}\rfloor=\frac{\lfloor\sqrt{4p+1}\rfloor-1}{2}$

又 $i=2a-2=2(a-1)$ ，所以 $i=\lfloor\sqrt{4p+1}\rfloor-1$

当 $i$ 为单数时，同理有 $i=\lfloor\sqrt{4p+1}\rfloor-1$，证明方法与上面类似。

$a_{p}=\lfloor\sqrt{4p+1}\rfloor-1$ （代码中的 $topoint$ 函数）

接下来就简单了。我们枚举每一个 $a_{p}$ 的不同的值 $i$，并求出到底有多少个 $a_{p}$ 需要我们累加到答案中（即下面代码里面的 $cnt$ ）即可。为了求出 $cnt$ ，我们可以求出上一个被加入答案的地方 $last$（它可以从上一个枚举的 $i$ 那里继承，第一个 $last=r$），并求出这一段（定义 $a_{p}$ 值相同的为一段）的右端 $rl$，则有：

$cnt=((rl-last)/m+1)$

好了，现在万事俱备，但还是有两个点要注意：

1.极限数据（如$n=10^{13},m=1,r=0$）会爆long long或unsigned long long，使用__int128可以解决

2.由于 $c++$ 自带的sqrt()常数很大，多次调用可能超时，所以我们要尽量不要再循环里面使用（ 你猜我考场上怎么挂分的 ）。代码中有注释。

#include<bits/stdc++.h>
using namespace std;
inline long long read()//快读函数，可以快速读取（输入） 
{
	long long s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	} 
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
	return s*w;
}
long long topoint(long long a)
{
	long long res=(long long)floor(sqrt(a*4+1))-1;
	return res;
}
void write(__int128 x)
{
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
int t;
int main()
{
	//freopen("discrimination.in","r",stdin);
	//freopen("discrimination.out","w",stdout);
	scanf("%d",&t);
	while(t--)
	{
		long long n,m,r;
		__int128 ans=0;
		n=read();
		m=read();
		r=read();
		if(!r) r+=m;
		long long last=r;
		for(long long i=topoint(r);i<=topoint(n)&&last<=n;i++)
		{
			while((i+2)*(i+2)<=4*last+1) i++;
			//若42行改成i=topoint(last);则仍然正确，因为两者是等价的，但会TLE（80pts）
			bool flag=(i%2==1);
			long long a=(i+2)/2,rl=min(n,flag==1?a*a+a-1:a*a-1);
			long long cnt=((rl-last)/m+1);
			ans+=cnt*i;
			last+=cnt*m;
		}
		write(ans);
		printf("\n");
	}
}