专栏文章

题解：P11397 界分数

mmalinhao45
P11397题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqqsc1y
此快照首次捕获于
2025/12/04 09:13
3 个月前
此快照最后确认于
2025/12/04 09:13
3 个月前
查看原文
此题首先考虑贪心。这道题有两个操作：
  1. 分子分母都加 11。
  2. 分子加 11。
如果可以约分就约分。它要求的是 f(x)=∑i=1n f(i)f(x) = \sum_{i = 1}^{n} \ f(i) ， f(i)=f(i)= 上面操作的最小值。
我们可以猜想一个结论：约分次数越多，操作数量越小。约分的公因数越小，操作数量越小。而每个数的因数都有 11 ，所以 11 不能够约分。所以我们就要整出来公因数—— 22。当然，如果分子分母都是偶数，肯定是能直接约分。如果只有分子是奇数或 00，只需用到操作 22 即可，如果分子分母都是奇数，那就用到了操作 11。至于为什么不用考虑只有分母是奇数的情况，请读者自己考虑。
证明：如果要让分数的值变为 11 时，必须让分子和分母相等。而分子只能 11 个 11 个地累加，所以说分母越小，操作数量越小。重要使分母变小的措施是约分。而约分的分子越大，所需要用到的操作次数越多，所以那明显是不优的。所以我们要让公因数为 22。所以说，上文的猜想是正确的。还有，我们考虑的约分的公因数是质数，因为合数在出现之前就已经被约分了。就像质因数分解一样。而质数没有第 33 个因数，所以如果要想使分子分母都有这个公共质因数 xx 的话，f(x)f(x) 的值至少是 xx。我们要求 f(x)f(x) 的最小值，所以这个质数越小，f(x)f(x) 越小，所以我们选取最小的质数 22。
通过上述这些，我们可以迅速地写出一个模拟的代码：
CPP
#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;
}
在赛时喜提了九十分的好成绩。
我发现最后全都超时了。考虑优化。 可以通过输出 cntcnt 的每次值，可以得到以下数据打表数据。

在数据中，一共有 22 个 33，44 个 44，88 个 55，1616 个 66，3232 个 77。

规律就是 2n1−22 ^ {n1-2} 个 n1。
我们可以得出代码：
CPP
#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;
}
代码中 xx 代指是 22 的几次方，cccc 表示上文中 n1。当 nn 的个数不够 xx 时，就把答案加上 n×ccn\times cc 即可。
却还是九十分 因为 n≤1018n \le 10^{18}， long long 存不下了，所以要用 unsigned long long。
CPP
#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分。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...