Submission #60736758

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int MAX_VAL = 20000000;
vector<int> precompute_f() {
    vector<int> f(MAX_VAL + 1);
    for (int i = 1; i <= MAX_VAL; ++i) {
        int x = i;
        while (x % 2 == 0) {
            x /= 2;
        }
        f[i] = x;
    }
    return f;
}
int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
const int MAX_VAL = 20000000;
vector<int> precompute_f() {
    vector<int> f(MAX_VAL + 1);
    for (int i = 1; i <= MAX_VAL; ++i) {
        int x = i;
        while (x % 2 == 0) {
            x /= 2;
        }
        f[i] = x;
    }
    return f;
}
int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    vector<int> f = precompute_f();
    unordered_map<int, long long> freq;
    for (int i = 0; i < N; ++i) {
        freq[A[i]]++;
    }
    long long result = 0;
    for (auto &[x, count1] : freq) {
        for (auto &[y, count2] : freq) {
            if (x > y) continue;
            int sum = x + y;
            if (sum <= MAX_VAL) {
                long long f_sum = f[sum];
                if (x == y) {
                    result += f_sum * count1 * (count1 + 1) / 2;
                } else {
                    result += f_sum * count1 * count2;
                }
            }
        }
    }
    cout << result << endl;
    return 0;
}

Submission Info

Judge Result