题解：P11397 界分数

· · 题解

此题首先考虑贪心。这道题有两个操作：

  1. 分子分母都加 1。
  2. 分子加 1。

如果可以约分就约分。它要求的是 f(x) = \sum_{i = 1}^{n} \ f(i) ， f(i)= 上面操作的最小值。

我们可以猜想一个结论：约分次数越多，操作数量越小。约分的公因数越小，操作数量越小。而每个数的因数都有 1 ，所以 1 不能够约分。所以我们就要整出来公因数—— 2。当然，如果分子分母都是偶数，肯定是能直接约分。如果只有分子是奇数或 0，只需用到操作 2 即可，如果分子分母都是奇数，那就用到了操作 1。至于为什么不用考虑只有分母是奇数的情况，请读者自己考虑。

证明：如果要让分数的值变为 1 时，必须让分子和分母相等。而分子只能 1 个 1 个地累加，所以说分母越小，操作数量越小。重要使分母变小的措施是约分。而约分的分子越大，所需要用到的操作次数越多，所以那明显是不优的。所以我们要让公因数为 2。所以说，上文的猜想是正确的。还有，我们考虑的约分的公因数是质数，因为合数在出现之前就已经被约分了。就像质因数分解一样。而质数没有第 3 个因数，所以如果要想使分子分母都有这个公共质因数 x 的话，f(x) 的值至少是 x。我们要求 f(x) 的最小值，所以这个质数越小，f(x) 越小，所以我们选取最小的质数 2。

通过上述这些，我们可以迅速地写出一个模拟的代码：

#include<bits/stdc++.h>
#define mod 998244353
#define int long long
using namespace std;
int n;
signed main() {
    cin>>n;
    int ans=0;
    for(int i=1; i<=n; i++) {
        int t=i;
        int cnt=1;
        while(t!=1) {
            t=(t+1)/2;
            cnt++;
        }
        ans=ans%mod+cnt%mod;
    }
    cout<<ans%mod<<endl;
}

在赛时喜提了九十分的好成绩。

我发现最后全都超时了。考虑优化。 可以通过输出 cnt 的每次值，可以得到以下数据打表数据。

在数据中，一共有 2 个 3，4 个 4，8 个 5，16 个 6，32 个 7。

规律就是 2 ^ {n1-2} 个 n1。

我们可以得出代码：

#include<bits/stdc++.h>
#define mod 998244353
#define int long long
using namespace std;
int n;
signed main() {
    cin>>n;
    int ans=3;
    n-=2;
    int x=2;
    int cc=3;
    while(n-x>=0) {
        n-=x;
        ans=ans%mod+cc*x%mod;
        ans%=mod;
        x*=2;
        cc++;
    }
    ans=ans%mod+n%mod*cc%mod;
    cout<<ans%mod;
}

代码中 x 代指是 2 的几次方，cc 表示上文中 n1。当 n 的个数不够 x 时，就把答案加上 n\times cc 即可。

却还是九十分 因为 n \le 10^{18}， long long 存不下了，所以要用 unsigned long long。

#include<bits/stdc++.h>
#define mod 998244353
#define int unsigned long long
using namespace std;
int n;
signed main() {
    cin>>n;
    int ans=3;
    n-=2;
    int x=2;
    int cc=3;
    long long m=n-x;
    while(m>=0) {
        n-=x;
        ans=ans%mod+cc%mod*x%mod;
        ans%=mod;
        x*=2;
        cc++;
        m=n-x;
    }
    ans=ans%mod+n%mod*cc%mod;
    cout<<ans%mod;
}

最后得到了100分。