自动搬运

查看原文

来自洛谷，原作者为

	yummy 这个人是时代的眼泪，什么也没有留下

搬运于2025-08-24 23:07:00，当前版本为作者最后更新于2024-12-18 13:39:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

结论

第一步纯分子 $+1$。从 $\dfrac{1}{x}$ 开始，每次：

• 若 $x$ 是奇数，则分子和分母都 $+1$。
• 若 $x$ 是偶数，则分子 $+1$。

这样，每次 $x$ 都会变成 $\lceil x/2 \rceil$，总步数为 $\lceil \log_2 x\rceil+1$。

感性理解的缺陷

一个常见的感性理解是：

• 由于 $\dfrac{\log_2 n}{n-1}$ 在 $n=2$ 时取最大值，因此每次约分约掉 $2$ 的“性价比”是最高的。
• 约掉相同的 $\gcd$，约分的时机越早，$+1$ 次数越小。

然而这些感性理解有一些问题，包括但不限于：

• 完全没有考虑约分后分子不是 $1$ 的情形，如 $\dfrac{1}{5},\dfrac{2}{5},\dfrac 3 5,\dfrac 2 3, \dfrac 1 1$ 这种路径为什么一定不优。
• 背包问题告诉我们，性价比最大不代表总价值最大。
• 事实上，如果初始分子不是 $1$，结论完全不长这样，但是你能写一个类似的“感性理解”出来，说明确实还有逻辑漏洞。

出题人也给过我一些补丁，但是打上补丁之后，因为无法穷尽所有可能的策略，所以仍然有一些新问题。

参考证明

下面的论证均从 $\dfrac{1}{x}$ 开始。

设 $a_i$ 为第 $i$ 步 $+1$ 前的分母，$b_i$ 为第 $i$ 步 $+1$ 前的分子，并且最优方案用了 $n$ 步。

根据定义，$a_1=x$，$b_1=1$，且 $a_n=b_n=1$，并且：

• $\forall 1\le i<n$，存在 $1\le k_i<b_{i}+1$ 使得 $b_{i+1}=\dfrac{b_i+1}{k_i}$（分子固定 $+1$）
• 此时必有 $\dfrac{a_i}{k_i}\le a_{i+1}\le \dfrac{a_{i}+1 }{k_i}$。

Lemma $\sum\limits_{i=1}^{n-1} k_i \le 2n-2$。

Proof 依题意，$b_{i+1}k_i = b_i+1$，得到 $b_{i+1}(k_i-1) = b_i-b_{i+1}+1$，从而 $k_{i}-1\le b_i-b_{i+1}+1$。把 $-1$ 移项后对两边求和，有 $\sum\limits_{i=1}^{n-1} k_i \le b_1-b_n + (2n-2)=2n-2$。

Proof of theorem 由数学归纳法，有 $x=a_1 \le \prod\limits_{i=1}^{n-1} k_i$。只需证明所有 $k_i$ 都是 $2$ 的时候，$\prod\limits_{i=1}^{n-1} k_i$ 最大，就可以证明 $n\ge \lceil \log_2 x \rceil$。

若有的 $k_i$ 不是 $2$，由于所有 $k_i$ 总和是 $2n-2$，则至少存在一对 $k_p=1,k_q>2$。此时 $(k_p+1)(k_q-1)=k_pk_q+(k_q-k_p-1) >k_pk_q$，从而这个 $k_i$ 不是最大的。

由于 $2n-2$ 的划分方案数是有限的，因此最大值必然存在。从而，最大值在 $k_i$ 全是 $2$ 时取到。

参考代码

#include<bits/stdc++.h>
using namespace std;
const long long Mod=998244353;
int main(){
	long long n,ans=1;
	scanf("%lld",&n);
	for(int i=0;i<=61;i++){
		long long l=(1ll<<i)+1,r=min(n,2ll<<i);
		if(l>n)break;
		ans=(ans+(r-l+1)%Mod*(i+2))%Mod;
	}
	printf("%lld\n",ans);
	return 0;
}