专栏文章

题解：P12183 DerrickLo's Milk Loong (UBC002F)

ccosf
P12183题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mipma88f
此快照首次捕获于
2025/12/03 14:19
3 个月前
此快照最后确认于
2025/12/03 14:19
3 个月前
查看原文

UBC002F

先说结论：极差最大只有 33。具体证明较为复杂，放在最后。这里先放一个计算机验证的链接，代码在题面里，保证在数据范围内有解。
令 Δ\Delta 表示极差，vv 表示序列中出现的最小数，a,b,c,da, b, c, d 分别表示 v,(v+1),(v+2),(v+3)v, (v + 1), (v + 2), (v + 3) 的出现次数，令 sum\text{sum} 表示 ∑i=1nai\sum_{i=1}^na_i。
由于太多根号了码起来麻烦，为了简写，(x)1=x3,(x)2=x,(x)3=x2(x)_1 = \sqrt[3]{x}, (x)_2 = \sqrt{x}, (x)_3 = \sqrt{x^2}。R(x)\text{R}(x) 表示值 xx 的值域。
下面的方法给出了如何构造一组解。

Δ≤1\Delta \le 1

当 Δ=0\Delta = 0 时，a=n,lcm=v,sum=nva = n, \text{lcm} = v, \text{sum} = nv，所以 n=1n = 1，舍。
当 Δ=1\Delta = 1 时，a,b≥1a, b \ge 1，显然 lcm=v(v+1)\text{lcm} = v(v + 1)，有：
{a+b=n(1)av+b(v+1)=v(v+1)(2)\begin{cases} a + b = n & (1)\\ av + b(v + 1) = v(v + 1) & (2) \end{cases}
(2) mod v(2) \bmod v 得到 b≡0(modv)b \equiv 0 \pmod v。又 b(v+1)∈(0,v(v+1))b(v + 1) \in (0, v(v + 1))，因此 b∈[1,v−1]b \in [1, v - 1]，无解。

Δ=2\Delta = 2

如果 b=0b = 0，类似 Δ=1\Delta = 1 的情况，无解。
因此 a,b,c≥1a, b, c \ge 1。此时要分两类讨论。

1) v≡0(mod2)v \equiv 0 \pmod 2

此时 lcm=v×(v+1)(v+2)2\text{lcm} = v \times \frac{(v + 1)(v + 2)}{2}。考虑方程：
{a+b+c=n(3)av+b(v+1)+c(v+2)=v×(v+1)(v+2)2(4)\begin{cases} a + b + c = n & (3)\\ av + b(v + 1) + c(v + 2) = v \times \frac{(v + 1)(v + 2)}{2} & (4) \end{cases}
(4)−(3)×v(4) - (3) \times v 得到：
b+2c=v((v+1)(v+2)2−n)=f1(v)b + 2c = v(\frac{(v + 1)(v + 2)}{2} - n) = f_1(v)\\
由 (3)(3) 易得 R(b+2c)⊂[3,2n−1]\text{R}(b + 2c) \sub [3, 2n - 1]。代入计算，有 f1((2n)2−2)<3<2n−1<f1((2n)2)f_1((2n)_2 - 2) \lt 3 \lt 2n - 1 \lt f_1((2n)_2)，因此 v∈((2n)2−2,(2n)2)v \in ((2n)_2 - 2, (2n)_2)。

2) v≡1(mod2)v \equiv 1 \pmod 2

此时 lcm=v×(v+1)×(v+2)\text{lcm} = v \times (v + 1) \times (v + 2)。方程化简之后有：
b+2c=v((v+1)(v+2)−n)=f2(v)b + 2c = v((v + 1)(v + 2) - n) = f_2(v)
由 R(b+2c)⊂[3,2n−1]\text{R}(b + 2c) \sub [3, 2n - 1] 且 f1((n)2−2)<3<2n−1<f1((n)2)f_1((n)_2 - 2) \lt 3 \lt 2n - 1 \lt f_1((n)_2)，得 v∈((n)2−2,(n)2)v \in ((n)_2 - 2, (n)_2)。
可以观察到，这两个区间都很小（其中的整点数 ≤2\le 2），因此分别带入求解即可。接下来的分讨过程类似，所以就只保留结果了。并且，可以发现，如果 lcm\text{lcm} 的系数是 1k\frac{1}{k}，则根号 nn 前的系数就是 kk。这点可以加快求出范围的过程。

Δ=3\Delta = 3

仅有 v,(v+1),(v+3)v, (v + 1), (v + 3)

此时 lcm\text{lcm} 有四种可能。
v≡3(mod6)  ⟹  v∈((6n)2−2,(6n)2)v≡0(mod6)  ⟹  v∈((3n)2−2,(3n)2)v≡1,5(mod6)  ⟹  v∈((2n)2−2,(2n)2)v≡2,4(mod6)  ⟹  v∈((n)2−2,(n)2)\begin{aligned} v \equiv 3 \pmod 6 &\implies v \in ((6n)_2 - 2, (6n)_2)\\ v \equiv 0 \pmod 6 &\implies v \in ((3n)_2 - 2, (3n)_2)\\ v \equiv 1, 5 \pmod 6 &\implies v \in ((2n)_2 - 2, (2n)_2)\\ v \equiv 2, 4 \pmod 6 &\implies v \in ((n)_2 - 2, (n)_2)\\ \end{aligned}

仅有 v,(v+2),(v+3)v, (v + 2), (v + 3)

此时 lcm\text{lcm} 有四种可能。
v≡0(mod6)  ⟹  v∈((6n)2−2,(6n)2)v≡3(mod6)  ⟹  v∈((3n)2−2,(3n)2)v≡2,4(mod6)  ⟹  v∈((2n)2−2,(2n)2)v≡1,5(mod6)  ⟹  v∈((n)2−2,(n)2)\begin{aligned} v \equiv 0 \pmod 6 &\implies v \in ((6n)_2 - 2, (6n)_2)\\ v \equiv 3 \pmod 6 &\implies v \in ((3n)_2 - 2, (3n)_2)\\ v \equiv 2, 4 \pmod 6 &\implies v \in ((2n)_2 - 2, (2n)_2)\\ v \equiv 1, 5 \pmod 6 &\implies v \in ((n)_2 - 2, (n)_2)\\ \end{aligned}

四个数均有

注：后面发现，前面几种已经完全够了，即不需要这种情况。std 与后面的证明均不会提到此情况。
这个时候就不是 (kn)2(kn)_2 了，而是 (kn)3(kn)_3。带入就能发现式子从一个二次的变成了一个三次的。
lcm\text{lcm} 有两种可能的值：v(v+1)(v+2)(v+3)2\frac{v(v + 1)(v + 2)(v + 3)}{2} 与 v(v+1)(v+2)(v+3)6\frac{v(v + 1)(v + 2)(v + 3)}{6}。
v≡0(mod3)  ⟹  v∈((6n)1−2,(6n)1)v≡1,2(mod3)  ⟹  v∈((2n)1−2,(2n)1)\begin{aligned} v \equiv 0 \pmod 3 &\implies v \in ((6n)_1 - 2, (6n)_1)\\ v \equiv 1, 2\pmod 3 &\implies v \in ((2n)_1 - 2, (2n)_1)\\ \end{aligned}
至此，一共分了十四类。不过，去掉 Δ≤1\Delta \le 1 之后，本质不同的 vv 的取值只有 66 种，分别带入即可。求根可以用 <cmath> 库之类的来实现。大常数是乘给 O(1)O(1) 计算的，并不会影响 O(n)O(n) 的输出答案。另外，由于 vv 是根号级别，所以 vv 的和在 101010^{10} 量级左右，离 101210^{12} 很远。
下面是 DerrickLo 实现的 std。
CPP
#include<bits/stdc++.h>
#define lcm(a,b) ((a)*(b)/__gcd(a,b))
#define int long long
using namespace std;
int n;
vector<int>v2,v3;
int a1(int x){return cbrt(x);}
int a2(int x){return sqrt(x);}
int a3(int x){return cbrt(x*x);}
array<int,3> check3(int a,int b,int c,int p){
	//x+y+z=n,ax+by+cz=p
	int x=p-a*n;
	if(x<0)return{-1,-1,-1};
	if(b==a+1){
		int cc=x/(c-a);
		int bb=x%(c-a);
		if(cc==0)return {-1,-1,-1};
		if(bb==0){
			if(cc<=1)return {-1,-1,-1};
			cc--,bb+=c-a;
		}
		if(bb+cc<n)return {n-bb-cc,bb,cc};
		return{-1,-1,-1};
	}
	if(x<5)return {-1,-1,-1};
	int cc=x/3;
	if(x%3==0)cc--;
	if((x-3*cc)&1){
		if(cc==0)return{-1,-1};
		cc--;
	}
	int bb=(x-3*cc)/2;
	if(bb+cc<n)return {n-bb-cc,bb,cc};
	return {-1,-1,-1};
}
array<int,4> check4(int a,int b,int c,int d,int p){
	//x+y+z+w=n,ax+by+cz+dw=p
	int x=p-n*a;
	if(x<6)return {-1,-1,-1,-1};
	int dd=x/3-1,cc,bb;
	if(x-dd*3==3)bb=cc=1;
	if(x-dd*3==4)bb=1,cc=2;
	if(x-dd*3==5)bb=2,cc=1;
	if(bb+cc+dd<n)return {n-bb-cc-dd,bb,cc,dd};
	return {-1,-1,-1,-1};
}
signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=a2(2*n)-2;i<=a2(2*n);i++)if(i>0)v2.emplace_back(i);
	for(int i=a2(1*n)-2;i<=a2(1*n);i++)if(i>0)v2.emplace_back(i);
	for(int i=a2(6*n)-2;i<=a2(6*n);i++)if(i>0)v3.emplace_back(i);
	for(int i=a2(3*n)-2;i<=a2(3*n);i++)if(i>0)v3.emplace_back(i);
	for(int i=a2(2*n)-2;i<=a2(2*n);i++)if(i>0)v3.emplace_back(i);
	for(int i=a2(1*n)-2;i<=a2(1*n);i++)if(i>0)v3.emplace_back(i);
	for(int v:v2){
		auto now=check3(v,v+1,v+2,lcm(lcm(v,v+1),v+2));
		if(now[0]!=-1){
			for(int j=1;j<=now[0];j++)cout<<v+0<<"\t";
			for(int j=1;j<=now[1];j++)cout<<v+1<<"\t";
			for(int j=1;j<=now[2];j++)cout<<v+2<<" \n"[j==now[2]];
			return 0;
		}
	}
	for(int v:v3){
		auto now=check3(v,v+1,v+3,lcm(lcm(v,v+1),v+3));
		if(now[0]!=-1){
			for(int j=1;j<=now[0];j++)cout<<v+0<<" ";
			for(int j=1;j<=now[1];j++)cout<<v+1<<" ";
			for(int j=1;j<=now[2];j++)cout<<v+3<<" \n"[j==now[2]];
			return 0;
		}
		now=check3(v,v+2,v+3,lcm(lcm(v,v+2),v+3));
		if(now[0]!=-1){
			for(int j=1;j<=now[0];j++)cout<<v+0<<" ";
			for(int j=1;j<=now[1];j++)cout<<v+2<<" ";
			for(int j=1;j<=now[2];j++)cout<<v+3<<" \n"[j==now[2]];
			return 0;
		}
		auto noww=check4(v,v+1,v+2,v+3,lcm(lcm(lcm(v,v+1),v+2),v+3));
		if(noww[0]!=-1){
			for(int j=1;j<=noww[0];j++)cout<<v+0<<" ";
			for(int j=1;j<=noww[1];j++)cout<<v+1<<" ";
			for(int j=1;j<=noww[2];j++)cout<<v+2<<" ";
			for(int j=1;j<=noww[3];j++)cout<<v+3<<" \n"[j==now[2]];
			return 0;
		}
	}
	assert(0);
}
下面来一个证明。
我们需要证明所有的 nn 都存在一个 vv，可以对于所有的 vv，反推出对应 nn 的范围，只需看它们的并是不是 N∪[3,+∞)\N \cup [3, +\infty) 即可。
在 n≤56n \le 56 时可自行验证成立。下证 n≥57n \ge 57 的情况。下面的所有 kk 均属于 N+\N^+。
分六类讨论，即 vv 模 66 的余数。

1) v=6kv = 6k

Δ=2\Delta = 2

此时有 v((v+1)(v+2)2−n)∈[3,2n−1]v(\frac{(v + 1)(v + 2)}{2} - n) \in [3, 2n - 1]。
由 6k((6k+1)(3k+1)−n)≥36k((6k + 1)(3k + 1) - n) \ge 3 得：108k3+54k2+6k−3≥6kn108k^3 + 54k^2 + 6k - 3 \ge 6kn，保守估计，得 n≤18k2+9kn \le 18k^2 + 9k。
由 6k((6k+1)(3k+1)−n)≤2n−16k((6k + 1)(3k + 1) - n) \le 2n - 1 得：108k3+54k2+6k+1≤(6k+2)n108k^3 + 54k^2 + 6k + 1 \le (6k + 2)n，保守估计，得 n≥18k2+3k+1n \ge 18k^2 + 3k + 1。
因此 n∈[18k2+3k+1,18k2+9k]n \in [18k^2 + 3k + 1, 18k^2 + 9k]。

仅有 v,(v+1),(v+3)v, (v + 1), (v + 3)

此时有 v((v+1)(v+3)3−n)∈[4,3n−7]∪{3n−5}v(\frac{(v + 1)(v + 3)}{3} - n) \in [4, 3n - 7] \cup \{3n - 5\}，将 3n−53n - 5 忽略。
由 6k((6k+1)(2k+1)−n)≥46k((6k + 1)(2k + 1) - n) \ge 4 得：72k3+48k2+6k−4≥6kn72k^3 + 48k^2 + 6k - 4 \ge 6kn，有 n≤12k2+8kn \le 12k^2 + 8k。
由 6k((6k+1)(2k+1)−n)≤3n−76k((6k + 1)(2k + 1) - n) \le 3n - 7 得：72k3+48k2+6k+7≤(6k+3)n72k^3 + 48k^2 + 6k + 7 \le (6k + 3)n，有 n≥12k2+2k+1n \ge 12k^2 + 2k + 1。因此 n∈[12k2+2k+1,12k2+8k]n \in [12k^2 + 2k + 1, 12k^2 + 8k]。

仅有 v,(v+2),(v+3)v, (v + 2), (v + 3)

此时有 v((v+2)(v+3)6−n)∈{5}∪[7,3n−4]v(\frac{(v + 2)(v + 3)}{6} - n) \in \{5\} \cup [7, 3n - 4]。将 55 忽略。
则有：n∈[6k2+2k+1,6k2+5k]n \in [6k^2 + 2k + 1, 6k^2 + 5k]。

2) v=6k+1v = 6k + 1

Δ=2\Delta = 2 时 n∈[36k2+18k+3,36k2+30k+5]n \in [36k^2 + 18k + 3, 36k^2 + 30k + 5]。
不选 (v+2)(v + 2) 时 n∈[18k2+9k+2,18k2+18k+3]n \in [18k^2 + 9k + 2, 18k^2 + 18k + 3]。
不选 (v+1)(v + 1) 时 n∈[36k2+24k+4,36k2+42k+11]n \in [36k^2 + 24k + 4, 36k^2 + 42k + 11]。

3) v=6k+2v = 6k + 2

Δ=2\Delta = 2 时 n∈[18k2+15k+4,18k2+21k+5]n \in [18k^2 + 15k + 4, 18k^2 + 21k + 5]。
不选 (v+2)(v + 2) 时 n∈[36k2+30k+7,36k2+48k+14]n \in [36k^2 + 30k + 7, 36k^2 + 48k + 14]。
不选 (v+1)(v + 1) 时 n∈[18k2+18k+5,18k2+27k+14]n \in [18k^2 + 18k + 5, 18k^2 + 27k + 14]。

4) v=6k+3v = 6k + 3

Δ=2\Delta = 2 时 n∈[36k2+42k+13,36k2+54k+19]n \in [36k^2 + 42k + 13, 36k^2 + 54k + 19]。
不选 (v+2)(v + 2) 时 n∈[6k2+7k+3,6k2+10k+3]n \in [6k^2 + 7k + 3, 6k^2 + 10k + 3]。
不选 (v+1)(v + 1) 时 n∈[12k2+16k+6,12k2+22k+10]n \in [12k^2 + 16k + 6, 12k^2 + 22k + 10]。

5) v=6k+4v = 6k + 4

Δ=2\Delta = 2 时 n∈[18k2+27k+11,18k2+33k+14]n \in [18k^2 + 27k + 11, 18k^2 + 33k + 14]。
不选 (v+2)(v + 2) 时 n∈[36k2+54k+21,36k2+72k+82]n \in [36k^2 + 54k + 21, 36k^2 + 72k + 82]。
不选 (v+1)(v + 1) 时 n∈[18k2+30k+13,18k2+39k+20]n \in [18k^2 + 30k + 13, 18k^2 + 39k + 20]。

6) v=6k+5v = 6k + 5

Δ=2\Delta = 2 时 n∈[36k2+66k+31,36k2+78k+41]n \in [36k^2 + 66k + 31, 36k^2 + 78k + 41]。
不选 (v+2)(v + 2) 时 n∈[18k2+33k+16,18k2+42k+23]n \in [18k^2 + 33k + 16, 18k^2 + 42k + 23]。
不选 (v+1)(v + 1) 时 n∈[36k2+72k+36,36k2+90k+55]n \in [36k^2 + 72k + 36, 36k^2 + 90k + 55]。
至此，所有类别均讨论完成。
将所有 36k236k^2 项并起来：[36k2+18k+3,36k2+90k+55][36k^2 + 18k + 3, 36k^2 + 90k + 55]。循环下来，缺了一个 36k2+90k+5636k^2 + 90k + 56。
将所有 18k218k^2 项并起来：[18k2+3k+1,18k2+9k]∪[18k2+9k+2,18k2+42k+23][18k^2 + 3k + 1, 18k^2 + 9k] \cup [18k^2 + 9k + 2, 18k^2 + 42k + 23]。循环缺 18k2+9k+118k^2 + 9k + 1。
观察缺的项，36k236k^2 缺的数模 99 余 22，而 18k218k^2 缺的数模 99 余 11，所以它们不会相等。因此，所有数都可以在 Δ≤3\Delta \le 3 的情况下表示出来！
证毕。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...