B. Make Array Good
https://codeforces.com/problemset/problem/1762/B
思路
- 将不是\(2^n(n>0)\)的数构造成最小的一个大于\(a[i]\)的\(2^n\)，
证明：
代码
点击查看代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<cctype>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long LL;
const char nl = '\n';
const int N = 1e5+10;
const int M = 2e5+10;
int a[N];
void solve(){
int t;
cin >> t;
while(t -- ){
int n;
cin >> n;
vector<pair<int,LL>> v;
for(int i = 1; i <= n; i ++ ){
cin >> a[i];
if(__builtin_popcount(a[i]) != 1 && a[i] != 1){
v.push_back({i,(1ll << (32 - __builtin_clz(a[i]))) - a[i]});
}
}
cout << v.size() << nl;
for(auto u:v){
cout << u.X << " " << u.Y << nl;
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
solve();
}
二进制运算一些技巧
__builtin_popcount(a[i]) != 1->不是2的幂1ll << (32 - __builtin_clz(a[i])最小的一个大于a[i]的2的幂
公因数（数论角度）
- 原题条件可由大数被小数整除转化为小数是大数和小数的最大公因数
- 所有\(2^n（n > 0）\)的数最大公因数都为小数