C++写Bob has a magic computer which has infinite USB ports. But there is a problem with this computer——it can only read and write the two most recently inserted USB disks. Initially, Bob has n USB disks and every USB disk has one unique file. He wants to insert all the n USB disks into his computer. Since his computer is old, he must insert USB disk in the following way: Select 2 unplugged USB disks, insert them into computer. The two USB disks inserted in the previous step will share the files with each other, which means after that both two USB disks will have all files either in the first one or in the second one. If all the n USB disks are in the computer, the task is finished. Otherwise, choose one USB disk in the computer, unplug it and go to step 1 . Bob wants to know the minimum number of n such that there is a sequence of operations that ends up with at least k different files in each USB disk. Input Only one number,k (2≤k≤100000 ),meaning that finally each USB disk owns at least k different files. Output You need to output one number n , which means the minimum number of USB disks in module 998244353.
时间: 2024-01-31 16:01:52 浏览: 95
以下是C++代码实现:
```cpp
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int mod = 998244353;
int k, n = 1;
int main() {
scanf("%d", &k);
while(n < k) n <<= 1;
printf("%d\n", (2 * n - k) % mod);
return 0;
}
```
首先,我们可以观察到,每次插入两个USB时,每个USB上的文件数都至少增加1,因此,如果最终每个USB上至少有k个文件,那么n个USB上的文件数之和至少为kn。
其次,我们可以发现,最终每个USB上的文件数相同,因此,每个USB上的文件数都是kn/n=k。
因此,我们可以考虑从第一次插入USB开始,每次将两个USB上的文件数合并,直到所有的n个USB上的文件数都相同且均为k。每次合并两个USB时,文件数至少增加1,因此,需要合并的次数为2n-k。最终答案即为2n-k对998244353取模的结果。
注意,n需要取到大于等于k的最小的2的幂次方。
阅读全文