题解：P11397 界分数

yummy · 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，并且：

• 此时必有 \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;
}