Submission #72187126

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, s, e) for (ll i = (ll)(s); i < (ll)(e); ++i)
#define rrep(i, s ,e) for (ll i = (ll)(s); i > (ll)(e); --i)
using namespace std;
typedef long long ll;
const ll INF = 1LL << 60;
const ll MOD = 998244353;
//const ll MOD = 1000000007;


template <typename T>
vector<T> compress(vector<T> &X) {
    vector<T> vals = X;
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    for (int i = 0; i < (int)X.size(); i++) {
        X[i] = lower_bound(vals.begin(), vals.end(), X[i]) - vals.begin();
    }
    return vals;
}

template <typename T>
struct SegmentTree {
private:
    int n;
    vector<T> node;
    T e = 0;
public:
    SegmentTree(vector<T> v) {
        ll sz = (ll)v.size();
        n = 1; while(n < sz) n *= 2;
        node.resize(2*n-1, e);

        for(ll i=0; i<sz; i++) node[i+n-1] = v[i];
        for(ll i=n-2; i>=0; i--) node[i] = merge(node[i*2+1],node[i*2+2]);
    }

    T merge(T a,T b){
        return max(a,b);
    }
    void update(ll k, T val) {
        k += (n - 1);
        node[k] = val;


        while(k > 0) {
            k = (k - 1) / 2;
            node[k] = merge(node[2*k+1],node[2*k+2]);
        }
    }

    T query(ll a, ll b, ll k=0, ll l=0, ll r=-1) {
        if(r < 0) r = n;
        if(b <= l || r <= a) return e;
        if(a <= l && r <= b) return node[k];

        T vl = query(a, b, 2*k+1, l, (l+r)/2);
        T vr = query(a, b, 2*k+2, (l+r)/2, r);
        return merge(vl,vr);
    }
 T operator[](ll at){
        at += n-1;
        return node[at];
    }


};


int main(){
    cin.tie(0);cout.tie(0);
    ios_base::sync_with_stdio(false);

    ll n;cin >> n;
    ll N = 10000000;
    vector<ll> v(N+1);
    for(ll i=1;i*i <= N;i++){
        for(ll j=i+1;j*j <= N;j++){
            if(i*i+j*j <= N)v[i*i+j*j]++;
        }
    }
    vector<ll> ans;
    rep(i,1,n+1){
        if(v[i] == 1)ans.push_back(i);
    }
    cout << ans.size() << endl;
    for(auto x:ans)cout << x << " ";
    cout << endl;
}

Submission Info

Judge Result