Submission #490973

#TimeUsernameProblemLanguageResultExecution timeMemory
490973duchungToys (CEOI18_toy)C++17
59 / 100
1773 ms262148 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1e7 + 5; int n; map<pair<int , int> , bool> visited; vector<int> Div[N]; vector<int> ans; void calc(int x) { if (x > 1e7) return; for (int i = 1 ; i * i <= x ; ++i) { if (x % i == 0) { if (i != 1) Div[x].push_back(i); if (i * i != x && x / i != 1) Div[x].push_back(x / i); } } } void build() { for (int i = 1 ; i * i <= n ; ++i) { if (n % i == 0) { calc(i); if (i * i != n) calc(n / i); } } } void backtrack(int n , int sum) { if (visited[{n , sum}] == true) return; visited[{n , sum}] = true; if (n == 1) return; if (n <= 1e7) { for (int x : Div[n]) backtrack(n / x , sum + x - 1); } else { for (int i = 1 ; i * i <= n ; ++i) { if (n % i == 0) { if (i != 1) backtrack(n / i , sum + i - 1); if (i * i != n && n / i != 1) backtrack(i , sum + n / i - 1); } } } } int main() { // freopen(".inp","r",stdin); // freopen(".out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; build(); backtrack(n , 0); for (auto x : visited) { if (x.first.first == 1) ans.push_back(x.first.second); else break; } cout << ans.size() << "\n"; for (int x : ans) cout << x << " "; }
#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...