CF1762B Make Array Good 题解

题目传送门

思路

题目中存在条件：$0 \le p\le n$，因此我们可以把所有数字都修改一次。

题目中规定，任意两个数都是倍数关系。我们便可以将每个数变成 $2^k$（$k$ 为非负整数）。

题目中还说，$0 \le x \le a_i$，所以，一定可以将 $a_i$ 加上一个数字，使它变为 $2^k$。

找到大于 $a_i$ 的最小的 $2^k$，使 $a_i$ 变成这个数字即可。

代码

#include<bits/stdc++.h>
using namespace std;
void solve()
{
	int n;cin>>n;
	cout<<n<<endl;
	for(int i=1;i<=n;i++)
	{
		int x;cin>>x;
		int k=1;
		while(k<=x) k*=2;//找到大于a[i]，最小的2^k
		cout<<i<<" "<<k-x<<endl;//将a[i]加上k-a[i]，此时a[i]变为k
	}
	
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
	return 0; 
}
 

---