牛牛与2的幂次方题解

题解：
根据题意，最简单的思路就是把这n个数全部两两加起来，然后依次判断和是否是2的幂次方，只不过时间复杂度过高，在题目所给的n范围内无法通过；
再思考思考， ,
移项可得:
所以我们可以这样只需要枚举 ;
然后用 在剩余的a[i + 1] ~ a[n - 1]个数中查找存在多少个 就可以解决问题了。
由于给定的ai <= 1e9, 即ai + aj< 2^31,所以x枚举的时候只需要枚举0到30就足够了。
查找的时候可以利用二分查找来优化查找时间。
使用low来记录第一个大于等于key的位置、使用up来记录第一个大于key的位置，那么两个位置的差就是数列中key的个数。
注意，结果会爆int，需要long long记录。
时间复杂度
空间复杂度

/**
 * 返回n个数中一共有多少对数之和为2的幂次方
 * @param n int整型 代表一共有多少数
 * @param a int整型vector 代表每个数字的大小
 * @return long长整型
 */
long long solve(int n, vector<int> &a)
{
    // write code here
    int atw[33] = {0};
    for (int i = 0; i <= 30; i++)
        atw[i] = 1 << i;      
    sort(a.begin(), a.end()); 
    long long ans = 0;
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = 0; j <= 30; j++)
        {
            int key = atw[j] - a[i];
            int low = lower_bound(a.begin() + i + 1, a.end(), key) - a.begin(); 
            int cnt = 0;
            if (a[low] == key)
            {                                                                      
                int up = upper_bound(a.begin() + i + 1, a.end(), key) - a.begin(); 
                cnt = up - low;                                                    
            }
            ans += cnt;
        }
    }
    return ans;
}