Powers of Two [Codeforces 教育15 : B]

問題

http://codeforces.com/contest/702/problem/B

n個の数aiがある。
ここから2つ選んだ和が2の累乗である組合せは何通りか

1 <= n <= 10^5
1 <= ai <= 10^9

考察

1. 普通に2つ選ぶと O(n^2) でダメそう
2. 和は2*10^9を超えないので、2の累乗はあまりなさそう
3. 2^31 > 2 * 10^9 なので31個ある

4. 個数を数えておき、それを用いることにする
5. 2の累乗 x と片方の数 a が決まれば、もう片方の数は x - a と一意に定まる
6. こうすることで、考えるべき組合せは、O(31n)となり計算できる範疇になる

実装

http://codeforces.com/contest/702/submission/19521073

typedef long long ll;
//-----------------------------------------------------------------
int n;
int a[101010];
//-----------------------------------------------------------------
int main() {
	cin >> n;
	rep(i, 0, n) scanf("%d", &a[i]);

	map<ll, ll> cnt;
	rep(i, 0, n) cnt[a[i]]++;

	set<int> _set;
	rep(i, 0, n) _set.insert(a[i]);

	ll x = 1;
	ll ans = 0;
	rep(i, 0, 32) {
		for (int j : _set) if (j <= x) {
			if (j == x)
				ans += cnt[x] * (cnt[x] - 1) / 2;
			else
				ans += cnt[j] * cnt[x * 2 - j];
		}
		x *= 2;
	}
	cout << ans << endl;
}