acm-(构造、数学、好题)2020ICPC·小米 网络选拔赛第一场 K. Sqrt Approaching
传送门
一道神仙构造题，首先将题目给的式子化解了，我们能得到
A
B
<
C
D
<
n
\frac AB<\frac CD<\sqrt n
BA<DC<n
或
n
<
C
D
<
A
B
\sqrt n<\frac CD<\frac AB
n
<DC<BA。
以第一个式子为例，由于
C
D
>
A
B
\frac CD>\frac AB
DC>BA,由于
C
,
D
C,D
C,D都是正数，不妨设
C
D
=
X
n
+
Y
B
n
+
Z
,
(
X
>
A
)
\frac CD=\frac{Xn+Y}{Bn+Z},(X> A)
DC=Bn+ZXn+Y,(X>A)，这样一定存在
X
,
Y
,
Z
X,Y,Z
X,Y,Z使得
C
D
>
A
B
\frac CD>\frac AB
DC>BA,不过本题难就难在这个构造上，而现在我们必须让
X
n
+
Y
B
n
+
Z
<
n
\frac{Xn+Y}{Bn+Z}<\sqrt n
Bn+ZXn+Y<n
才行，由于变量太多了，先让
Y
=
0
Y=0
Y=0吧，然后将这个式子我们随便化简一下就得到
X
n
<
B
n
+
Z
X\sqrt n<Bn+Z
Xn
<Bn+Z，然后到这里一般人就没头绪了。
所以关键是我们需要利用一个条件就是
A
B
<
n
\frac AB<\sqrt n
BA<n
，我们对这个式子变一下：
A
B
<
n
⇒
A
<
B
n
⇒
A
2
<
B
2
n
⇒
A
2
(
n
−
1
)
<
B
2
n
(
n
−
1
)
.
.
.
.
.
.
.
.
别
问
我
为
什
么
要
这
样
乘
，
不
过
题
目
保
证
了
(
n
>
2
)
所
以
n
−
1
>
1
，
关
系
一
定
是
对
的
⇒
A
2
n
+
B
2
n
<
(
B
n
)
2
+
A
2
⇒
A
2
+
B
2
<
B
2
n
+
A
2
n
⇒
A
2
+
B
2
+
2
A
B
<
B
2
n
+
A
2
n
+
2
A
B
⇒
(
A
+
B
)
2
<
(
B
n
+
A
n
)
2
⇒
A
+
B
<
B
n
+
A
n
⇒
(
A
+
B
)
n
<
B
n
+
A
\begin{aligned} &\frac AB<\sqrt n\\ &\Rightarrow A<B\sqrt n\\ &\Rightarrow A^2<B^2n\\ &\Rightarrow A^2(n-1)<B^2n(n-1)........别问我为什么要这样乘，不过题目保证了(n>2)所以n-1>1，关系一定是对的\\ &\Rightarrow A^2n+B^2n<(Bn)^2+A^2\\ &\Rightarrow A^2+B^2<B^2n+\frac {A^2}n\\ &\Rightarrow A^2+B^2+2AB<B^2n+\frac{A^2}n+2AB\\ &\Rightarrow (A+B)^2<(B\sqrt n+\frac A{\sqrt n})^2\\ &\Rightarrow A+B<B\sqrt n+\frac {A}{\sqrt n}\\ &\Rightarrow (A+B)\sqrt n<Bn+A \end{aligned}
BA<n
⇒A<Bn
⇒A2<B2n⇒A2(n−1)<B2n(n−1)........别问我为什么要这样乘，不过题目保证了(n>2)所以n−1>1，关系一定是对的⇒A2n+B2n<(Bn)2+A2⇒A2+B2<B2n+nA2⇒A2+B2+2AB<B2n+nA2+2AB⇒(A+B)2<(Bn
+n
A)2⇒A+B<Bn
+n
A⇒(A+B)n
<Bn+A
这个形式不正好符合
X
n
<
B
n
+
Z
X\sqrt n<Bn+Z
Xn
<Bn+Z这个式子吗！！！
所以我们可以得出
X
=
A
+
B
,
Z
=
A
X=A+B,Z=A
X=A+B,Z=A,再验证下是否满足
C
D
>
A
B
\frac CD>\frac AB
DC>BA,容易发现是满足的(因为
(
A
+
B
)
n
B
n
+
A
>
A
+
B
B
+
A
n
,
B
A
n
>
A
B
\frac{(A+B)n}{Bn+A}>\frac{A+B}{B+\frac An},\frac B{\frac An}>\frac AB
Bn+A(A+B)n>B+nAA+B,nAB>BA)。对于
n
<
C
D
<
A
B
\sqrt n<\frac CD<\frac AB
n
<DC<BA这种情况按照上面的步骤同样能够算出来相同的答案，因此直接高精输出即可。
不过到这里估计大部分人都还是一头雾水(我也一样 )，虽然看上面的推导没有丝毫问题，但总觉得这个构造的过程不可思议，莫名其妙，尤其是令
Y
=
0
Y=0
Y=0以及从
A
B
<
n
\frac AB<\sqrt n
BA<n
推导的这个操作非常的变态，那个乘
n
−
1
n-1
n−1更是莫名其妙。个人感觉做这种题最重要的就是不断尝试吧，以及寻找数感。
本题代码过于简单，就不贴了，可以直接写python，java也行，估计要慢不少。