正文
将原式 \(a_i+a_j=2^p\) 转化为 \(a_j=2^p-a_i\)，对于，每个 \(a_i\)，枚举 \(p\)，可以有效地降低时间复杂度。
设 \(num\leftarrow 0\)，若 \(2^p-a_i\) 存在相等的 \(a_j\)，则 \(num\leftarrow num+1\)，最后输出 \(n-num\)，可以通过 unordered_map 实现匹配。
代码：
#include<iostream>
#include<unordered_map>
#define gg long long
using namespace std;
const gg INF=2e9+5;
gg n,a[120005],ans;
unordered_map<gg,gg> s;
int main(){
ios::sync_with_stdio(false),cin.tie(0);
cin>>n;
for(gg i=1;i<=n;i++) cin>>a[i],s[a[i]]++;
for(gg i=1;i<=n;i++){
s[a[i]]--;
gg p=1;
bool flag=true;
while(p<=INF){
if(s[p-a[i]]>0) flag=false;
p<<=1;
}
if(flag) ans++;
s[a[i]]++;
}
cout<<ans;
}
提交记录。
后附
日志
v1.0 on 2022.11.11: 发布
标签：false,leftarrow,CodeForces,gg,num,1005,unordered From： https://www.cnblogs.com/wanguan/p/16884387.html