提出 #72181588

---

ソースコード 拡げる

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <tuple>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using ll = long long;
using ld = long double;
using namespace std;
#define endl "\n"
#define ff first
#define ss second

#define forn(i,n) for(int i=0;i<n;i++)
#define dbgv(v) cout<<#v<<" "<<v<<endl
#define dbga(a,n) forn(i,n-1) {cout<<a[i]<<' ';} cout<<a[n-1]<<'\n';
#define all(v) (v).begin(), (v).end()


const int N = 1e7 + 5;
int lp[N],c[N],st[N];
vector<int> pr;

void pre(){
    st[1]=0;
    for(int i=2;i<N;i++){
        if(lp[i]==0){
            lp[i]=i;
            c[i]=1;
            pr.push_back(i);
            if(i%4==3) st[i]=-1;
            else if(i==2) st[i]=0;
            else st[i]=1;
        }
        for(auto p:pr){
            if(p>lp[i]||(ll)i*p>=N) break;
            int x=i*p;
            lp[x]=p;
            if(lp[i]==p) c[x]=c[i]+1;
            else c[x]=1;
            
            int y=i;
            if(c[x]>1) y/=p;
            int ps=st[y];
            
            if(ps==-1){
                st[x]=-1;
            }else if(p==2){
                st[x]=ps;
            }else if(p%4==3){
                if(c[x]%2!=0) st[x]=-1;
                else st[x]=ps;
            }else{
                if(ps!=0) st[x]=-1;
                else{
                    if(c[x]==1) st[x]=1;
                    else if(c[x]==2) st[x]=2;
                    else st[x]=-1;
                }
            }
        }
    }
}

void solve(){
    int n;
    if(cin>>n){
        vector<int> ans;
        for(int i=1;i<=n;i++){
            if(st[i]==1||st[i]==2) ans.push_back(i);
        }
        cout<<ans.size()<<endl;
        int sz=ans.size();
        forn(i,sz){
            cout<<ans[i]<<(i==sz-1?"":" ");
        }
        cout<<endl;
    }
}

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

    int T = 1;
    while(T--){
        solve();
    }
    return 0;
}

提出情報

ジャッジ結果