P2320 [HNOI2006]鬼谷子的钱袋

$Hyperlink$Hyperlink

https://www.luogu.com.cn/problem/P2320

---

$Description$Description

求用若干个正整数表示$\forall i\in[1,n],i\in \mathbb{N}$∀i∈[1,n],i∈N的最小正整数个数以及这些正整数

这些正整数不能重复（除了1）

数据范围：$n\leq 10^9$n≤109

---

$Solution$Solution

记得背包的二进制拆分做法吗？用2的正整数次幂是一定能表示出这些数，不过在这道题还不是最优的，这种划分方法严格意义上是有$log_2n+1$log2​n+1个的，而正解的做法是妥妥的$log_2n$log2​n，所以会有误差

考虑分治，设$S_x$Sx​为符合题意的表示$x$x的正整数集合

对于一个数$x$x，如果它是偶数，那么我们必然可以把它分成两部分，$x/2$x/2和$x/2$x/2，也就是说答案是$\{x/2\}\cup S_{x/2}${x/2}∪Sx/2​

如果它是奇数，那么我们同样可以把它分成两部分，$x/2$x/2和$x/2+1$x/2+1
在随便打表找找规律，发现奇数的答案就是$\{x/2+1\}\cup S_{x/2}${x/2+1}∪Sx/2​的

注意到$x$x是正整数，所以把两部分的答案合并起来就是$\{(x+1)/2\}\cup S_{x/2}${(x+1)/2}∪Sx/2​

显然我们只需要每次向集合中加入$(x+1)/2$(x+1)/2这个元素，然后递归处理即可

时间复杂度：$O(log_2n)$O(log2​n)

---

$Code$Code

#include<cctype>
#include<cstdio>
#define LL long long
using namespace std;int n,j,a[40];
inline LL read()
{
	char c;LL d=1,f=0;
	while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
signed main()
{
	n=read();
	while(n) a[++j]=(n+1)>>1,n>>=1;
	printf("%d\n",j);
	for(register int i=j;i>0;i--) printf("%d ",a[i]);
}