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

· · 题解

UBC002F

先说结论：极差最大只有 3。具体证明较为复杂，放在最后。这里先放一个计算机验证的链接，代码在题面里，保证在数据范围内有解。

令 \Delta 表示极差，v 表示序列中出现的最小数，a, b, c, d 分别表示 v, (v + 1), (v + 2), (v + 3) 的出现次数，令 \text{sum} 表示 \sum_{i=1}^na_i。

由于太多根号了码起来麻烦，为了简写，(x)_1 = \sqrt[3]{x}, (x)_2 = \sqrt{x}, (x)_3 = \sqrt{x^2}。\text{R}(x) 表示值 x 的值域。

下面的方法给出了如何构造一组解。

\Delta \le 1

当 \Delta = 0 时，a = n, \text{lcm} = v, \text{sum} = nv，所以 n = 1，舍。

当 \Delta = 1 时，a, b \ge 1，显然 \text{lcm} = v(v + 1)，有：

\begin{cases} a + b = n & (1)\\ av + b(v + 1) = v(v + 1) & (2) \end{cases} ### $\Delta = 2

如果 b = 0，类似 \Delta = 1 的情况，无解。

因此 a, b, c \ge 1。此时要分两类讨论。

1) v \equiv 0 \pmod 2

此时 \text{lcm} = v \times \frac{(v + 1)(v + 2)}{2}。考虑方程：

\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} $$ b + 2c = v(\frac{(v + 1)(v + 2)}{2} - n) = f_1(v)\\ $$ 由 $(3)$ 易得 $\text{R}(b + 2c) \sub [3, 2n - 1]$。代入计算，有 $f_1((2n)_2 - 2) \lt 3 \lt 2n - 1 \lt f_1((2n)_2)$，因此 $v \in ((2n)_2 - 2, (2n)_2)$。 #### 2) $v \equiv 1 \pmod 2

此时 \text{lcm} = v \times (v + 1) \times (v + 2)。方程化简之后有：

b + 2c = v((v + 1)(v + 2) - n) = f_2(v)

由 \text{R}(b + 2c) \sub [3, 2n - 1] 且 f_1((n)_2 - 2) \lt 3 \lt 2n - 1 \lt f_1((n)_2)，得 v \in ((n)_2 - 2, (n)_2)。

可以观察到，这两个区间都很小（其中的整点数 \le 2），因此分别带入求解即可。接下来的分讨过程类似，所以就只保留结果了。并且，可以发现，如果 \text{lcm} 的系数是 \frac{1}{k}，则根号 n 前的系数就是 k。这点可以加快求出范围的过程。

\Delta = 3

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

此时 \text{lcm} 有四种可能。

\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)

此时 \text{lcm} 有四种可能。

\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)_3。带入就能发现式子从一个二次的变成了一个三次的。

$$ \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} $$ --- 至此，一共分了十四类。不过，去掉 $\Delta \le 1$ 之后，本质不同的 $v$ 的取值只有 $6$ 种，分别带入即可。求根可以用 `<cmath>` 库之类的来实现。大常数是乘给 $O(1)$ 计算的，并不会影响 $O(n)$ 的输出答案。另外，由于 $v$ 是根号级别，所以 $v$ 的和在 $10^{10}$ 量级左右，离 $10^{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); } ``` --- 下面来一个证明。 我们需要证明所有的 $n$ 都存在一个 $v$，可以对于所有的 $v$，反推出对应 $n$ 的范围，只需看它们的并是不是 $\N \cup [3, +\infty)$ 即可。 在 $n \le 56$ 时可自行验证成立。下证 $n \ge 57$ 的情况。下面的所有 $k$ 均属于 $\N^+$。 分六类讨论，即 $v$ 模 $6$ 的余数。 #### 1) $v = 6k

\Delta = 2

此时有 v(\frac{(v + 1)(v + 2)}{2} - n) \in [3, 2n - 1]。

由 6k((6k + 1)(3k + 1) - n) \ge 3 得：108k^3 + 54k^2 + 6k - 3 \ge 6kn，保守估计，得 n \le 18k^2 + 9k。

由 6k((6k + 1)(3k + 1) - n) \le 2n - 1 得：108k^3 + 54k^2 + 6k + 1 \le (6k + 2)n，保守估计，得 n \ge 18k^2 + 3k + 1。

因此 n \in [18k^2 + 3k + 1, 18k^2 + 9k]。

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

此时有 v(\frac{(v + 1)(v + 3)}{3} - n) \in [4, 3n - 7] \cup \{3n - 5\}，将 3n - 5 忽略。

由 6k((6k + 1)(2k + 1) - n) \ge 4 得：72k^3 + 48k^2 + 6k - 4 \ge 6kn，有 n \le 12k^2 + 8k。

由 6k((6k + 1)(2k + 1) - n) \le 3n - 7 得：72k^3 + 48k^2 + 6k + 7 \le (6k + 3)n，有 n \ge 12k^2 + 2k + 1。因此 n \in [12k^2 + 2k + 1, 12k^2 + 8k]。

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

此时有 v(\frac{(v + 2)(v + 3)}{6} - n) \in \{5\} \cup [7, 3n - 4]。将 5 忽略。

则有：n \in [6k^2 + 2k + 1, 6k^2 + 5k]。

2) v = 6k + 1

不选 $(v + 2)$ 时 $n \in [18k^2 + 9k + 2, 18k^2 + 18k + 3]$。 不选 $(v + 1)$ 时 $n \in [36k^2 + 24k + 4, 36k^2 + 42k + 11]$。 ### 3) $v = 6k + 2 不选 $(v + 2)$ 时 $n \in [36k^2 + 30k + 7, 36k^2 + 48k + 14]$。 不选 $(v + 1)$ 时 $n \in [18k^2 + 18k + 5, 18k^2 + 27k + 14]$。 ### 4) $v = 6k + 3 不选 $(v + 2)$ 时 $n \in [6k^2 + 7k + 3, 6k^2 + 10k + 3]$。 不选 $(v + 1)$ 时 $n \in [12k^2 + 16k + 6, 12k^2 + 22k + 10]$。 ### 5) $v = 6k + 4 不选 $(v + 2)$ 时 $n \in [36k^2 + 54k + 21, 36k^2 + 72k + 82]$。 不选 $(v + 1)$ 时 $n \in [18k^2 + 30k + 13, 18k^2 + 39k + 20]$。 ### 6) $v = 6k + 5 不选 $(v + 2)$ 时 $n \in [18k^2 + 33k + 16, 18k^2 + 42k + 23]$。 不选 $(v + 1)$ 时 $n \in [36k^2 + 72k + 36, 36k^2 + 90k + 55]$。 至此，所有类别均讨论完成。 将所有 $36k^2$ 项并起来：$[36k^2 + 18k + 3, 36k^2 + 90k + 55]$。循环下来，缺了一个 $36k^2 + 90k + 56$。 将所有 $18k^2$ 项并起来：$[18k^2 + 3k + 1, 18k^2 + 9k] \cup [18k^2 + 9k + 2, 18k^2 + 42k + 23]$。循环缺 $18k^2 + 9k + 1$。 观察缺的项，$36k^2$ 缺的数模 $9$ 余 $2$，而 $18k^2$ 缺的数模 $9$ 余 $1$，所以它们不会相等。因此，所有数都可以在 $\Delta \le 3$ 的情况下表示出来！ 证毕。