codeforce—702B:Powers of Two（map的简单应用）

STL

题面链接

题意

输入n(1 ≤ n ≤ 105)，接下来n个数(1 ≤ ai ≤ 10^9)，找出满足两个数的和为2的X次方的组数

样例

input
4
7 3 2 1
output
2
input
3
1 1 1
output
3

代码

#include<stdio.h>
#include<string.h>
#include<map>
#include<algorithm>
using namespace std;
int p[31];///预处理出2^i
int a[100010];
int main()
{
    int n,i,j;
    p[0]=1;
    for(i=1;i<31;i++)
        p[i]=p[i-1]*2;
    while(~scanf("%d",&n))
    {
        map<int,int>mp;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            mp[a[i]]++;
        }
        sort(a,a+n);
        long long ans=0;
        for(i=0;i<n;i++)
        {
            mp[a[i]]--;
            for(j=1;j<31;j++)
            {
                if(p[j]<a[i])
                    continue;
                int num=p[j]-a[i];
                if(mp.find(num)==mp.end())
                    continue;
                ans+=mp[num];
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}