题目描述
输入描述
输出描述
输出一个整数表示答案。
样例输入
5
2 4 6 7 8
样例输出
1
(只有下标(1, 3)满足条件)
思路分析
本题其实就是A - B数对的变形题
/*
lowbit(ai + aj) = ai + aj 就相当于,a1 + aj = 2 ^ k
我们第一层循环枚举ai,第二层循环枚举k,在两层循环中枚举aj,找到第一次和最后一次出现的位置,
他们之间的差就是对答案的贡献
*/
代码实现
#include <iostream>
#include<algorithm>
#include<cstring>
using i64 = long long;
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 res = 0;
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
sort(a + 1, a + 1 + n);
for(int i = 1; i <= n; i ++)
for(int k = 0; k <= 30; k ++)
{
int aj = (1 << k) - a[i];
// 找到aj第一次出现的位置(二分之后的r)
int l = i, r = n + 1;
while(l + 1 < r)
{
int mid = l + r >> 1;
if(a[mid] < aj) l = mid;
else r = mid;
}
int t = r;
// 找到aj最后一次出现的位置(二分之后的l)
l = i, r = n + 1;
while(l + 1 < r)
{
int mid = l + r >> 1;
if(a[mid] <= aj) l = mid;
else r = mid;
}
res += l - t + 1;
}
cout << res << endl;
return 0;
}