【20231009A】区分度题面&&题解

题面

题意概括

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

对于所有 $1 \leq i \leq k$ ，不同的 $⌊ \frac{k}{i} ⌋$ 的个数。

现希望求出 $\sum_{k \equiv r (m o d = m)}^{1 \leq k \leq n} a_{k}$ 的值

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

题解

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

那我们来看看 $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_{j = 2}^{\frac{i + 1}{2}} 2 j) + 1 = (\frac{i + 1}{2})^{2} + \frac{i + 1}{2} - 1$ ，且可以发现 $\frac{i + 1}{2} = c o u n t (a_{p} = i)$

当 $i$ 为双数时同理， $p = (\sum_{j = 2}^{\frac{i}{2}} 2 j) + 1 + \frac{i + 2}{2} = (\frac{i + 2}{2})^{2} - 1$ ，且可以发现 $\frac{i + 2}{2} = c o u n t (a_{p} = i)$

综上， $⌊ \frac{i + 2}{2} ⌋ = c o u n t (a_{p} = i)$ 。令 $a = c o u n t (a_{p} = i)$

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

当 $i$ 为双数时，有：

$(a - 1)^{2} + (a - 1) \leq p < a^{2}$

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

则 $a - 1 = ⌊ \frac{⌊ \sqrt{4 p + 1} ⌋ - 1}{2} ⌋$ ，显然有 $2 (a - 1) \leq ⌊ \sqrt{4 p + 1} ⌋ - 1 \leq 2 a - 1$

则 $2 a - 1 \leq ⌊ \sqrt{4 p + 1} ⌋ \leq 2 a$ ，又由于 $p < a^{2}$ ，则 $p \leq a^{2} - 1$ ，则 $4 p + 1 < 4 a^{2}$ ， $⌊ \sqrt{4 p + 1} ⌋ < 2 a$ ，

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

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

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

$a_{p} = ⌊ \sqrt{4 p + 1} ⌋ - 1$ （代码中的 $t o p o i n t$ 函数）

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

$c n t = ((r l - l a s t) / 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");
	}
}

上篇luogu CF510D Fox And Jumping 裴蜀定理例题题解

下篇欧拉图与欧拉回路