Submission #96392

#TimeUsernameProblemLanguageResultExecution timeMemory
96392easruiToys (CEOI18_toy)C++14
100 / 100
823 ms7092 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 1e5; int N,tmp,fac[MAX],num[MAX],selA[MAX],selB[MAX],posA,posB,cnt,res,ans,A,B,C; vector<int> pows[MAX]; set<int> S; bool isP[MAX]; void act(int cur, int val, int sum) { if(val>=cur) S.insert(sum+cur-1); if(cur==1) return; for(int i=2; i<=min(val,cur/i); i++){ if(cur%i) continue; if(i<=val) act(cur/i,i,sum+i-1); if(cur/i<=val) act(i,cur/i,sum+cur/i-1); } } int main() { ios_base::sync_with_stdio(0),cin.tie(0); cin >> N; act(N,N,0); cout << S.size() << '\n'; for(auto it : S) cout << it << ' '; /*tmp = N; for(int i=0; i<MAX; i++) isP[i] = true; for(int i=2; i*i<=N; i++){ if(isP[i]){ for(int j=2; j*j*i*i<=N; j++) isP[j*i] = false; if(tmp%i==0) fac[++cnt] = i; while(tmp%i==0){ num[cnt]++; tmp /= i; } } } if(tmp!=1){ fac[++cnt] = tmp; num[cnt]++; } for(int i=1; i<=cnt; i++){ pows[i].push_back(1); for(int j=1; j<=num[i]; j++){ pows[i].push_back(pows[i][j-1]*fac[i]); } } A = B = 1; S.insert(A+B+(N/A/B)); while(1){ for(posB= 1; posB <= cnt; posB++){ if(selB[posB]<num[posB]-selA[posB]){ selB[posB]++; B *= fac[posB]; break; } B /= pows[posB][num[posB]-selA[posB]]; selB[posB] = 0; } if(posB>cnt) break; S.insert(A+B+(N/A/B)); } while(1){ for(posA = 1; posA <= cnt; posA++){ if(selA[posA]<num[posA]){ selA[posA]++; A *= fac[posA]; break; } A /= pows[posA][num[posA]]; selA[posA] = 0; } if(posA>cnt) break; B = 1; S.insert(A+B+(N/A/B)); for(int pos = 1; pos <= cnt ; pos++) selB[pos] = 0; while(1){ for(posB= 1; posB <= cnt; posB++){ if(selB[posB]<num[posB]-selA[posB]){ selB[posB]++; B *= fac[posB]; break; } B /= pows[posB][num[posB]-selA[posB]]; selB[posB] = 0; } if(posB>cnt) break; S.insert(A+B+(N/A/B)); } } cout << S.size() << '\n'; for(auto it : S) cout << (it-3) << ' ';*/ }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...