Submission #73093570

---

Source Code Expand

// C
#include <bits/stdc++.h>
#define endl '\n'
#define MOD1 1000000007
#define MOD2 1000000009
#define R1 91138233
#define R2 97266353
#define int long long
using namespace std;

unordered_map<int, int> freq;
vector<int> pr;
int p1, p1t, p2, p2t, r1, r2;

int qpow(int a, int b, int mod){
    int res = 1;
    a %= mod;
    while(b){
        if(b & 1)
            res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

bool check(int n, int s){
    unordered_map<int, bool> f;
    for(int v : pr){
        if(v == n || f[v]) continue;
        if(v > n) return false;
        if(v == n - v){
            if(freq[v] % 2 != 0)
                return false;
        }
        else{
            int cnt1 = freq[v];
            auto it = freq.find(n - v);
            int cnt2 = (it == freq.end() ? 0 : it->second);
            if(cnt1 != cnt2)
                return false;
        }
        f[v] = true;
        if(v != n - v)
            f[n - v] = true;
    }
    return true;
}

int n, sum, maxx, a[300005];

signed main(){
    cin >> n;
    for(int i = 0;i < n;i++){
        cin >> a[i];
        sum += a[i];
        if(a[i] > maxx)
            maxx = a[i];
        freq[a[i]]++;
    }
    for(auto& p : freq)
        pr.push_back(p.first);
    r1 = qpow(R1, MOD1 - 2, MOD1);
    r2 = qpow(R2, MOD2 - 2, MOD2);
    p1 = p1t = p2 = p2t = 0;
    for(auto& p : freq){
        int v = p.first, w = p.second;
        int t1 = v % (MOD1 - 1);
        int t2 = qpow(R1, t1, MOD1);
        int t3 = qpow(r1, t1, MOD1);
        p1 = (p1 + w * t2) % MOD1;
        p1t = (p1t + w * t3) % MOD1;

        int t4 = v % (MOD2 - 1);
        int t5 = qpow(R2, t4, MOD2);
        int t6 = qpow(r2, t4, MOD2);
        p2 = (p2 + w * t5) % MOD2;
        p2t = (p2t + w * t6) % MOD2;
    }

    int ans[300005], cntans = 0, summ = 2 * sum;
    for(int i = n;i <= 2 * n;i++){
        if(summ % i != 0)
            continue;
        int tmp = summ / i;
        if(tmp < maxx)
            continue;
        int s = 0;
        auto it = freq.find(tmp);
        if(it != freq.end()) s = it->second;
        if(s != i - n)
            continue;

        int eL1 = tmp % (MOD1 - 1);
        int rL1 = qpow(R1, eL1, MOD1);
        int l1 = (p1 - rL1 * p1t) % MOD1;
        if(l1 < 0) l1 += MOD1;
        int r1 = (s * (rL1 - 1)) % MOD1;
        if(r1 < 0) r1 += MOD1;
        if(l1 != r1) continue;

        int eL2 = tmp % (MOD2 - 1);
        int rL2 = qpow(R2, eL2, MOD2);
        int l2 = (p2 - rL2 * p2t) % MOD2;
        if(l2 < 0) l2 += MOD2;
        int r2 = (s * (rL2 - 1)) % MOD2;
        if(r2 < 0) r2 += MOD2;
        if(l2 != r2) continue;

        if(check(tmp, s)) ans[cntans++] = tmp;
    }

    sort(ans, ans + cntans);
    for(int i = 0;i < cntans;i++)
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function 'bool check(long long int, long long int)':
./Main.cpp:27:23: warning: unused parameter 's' [-Wunused-parameter]
   27 | bool check(int n, int s){
      |                       ^

Judge Result