Acwing 2022 模拟赛

B

题意

给定一个正整数 (n) , 让你求最少需要多少个正整数，使得利用选取（部分或全部），可以组成 (1sim n) 之间的任意整数重量。

思路

乍一看，这道题目还是挺难的。但是静下心思考时，便会发现这是一道找规律题。
我们先手模一下当 (n = 1sim 8) 时的数据：

所以说当 (n) 为 (2) 的正整数次幂数时，答案就会比之前多一个。
这就是答案

证明

我们都知道一个规律，用 (2^0), (2^1) , (2^2) (dots) (2^n) 可以表示 (1dots 2^{n+1}-1)之内所有的数
所以当 (n) 为 (2) 的正整数幂便答案就要加 1 。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
	int n;
	cin>>n;
	int sum=0;
	while(n!=0){
		n/=2;
		sum++;
	}
	cout<<sum<<endl;
	return 0;
}