제출 #331437

#제출 시각아이디문제언어결과실행 시간메모리
331437davitmargToys (CEOI18_toy)C++17
59 / 100
19 ms19564 KiB
/* DavitMarg In a honky-tonk, Down in Mexico */ #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <random> #include <bitset> #include <stack> #include <cassert> #include <iterator> #define mod 1000000007ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() #define fastIO ios::sync_with_stdio(false); cin.tie(0) using namespace std; const int N = 100005; int n; set<int> ans; map<int, set<int>> dp[N]; map<int, int> used[N]; set<int> add(set<int> a,int d) { set<int> s; for (auto it = a.begin(); it != a.end(); ++it) s.insert(*it + d); return s; } set<int> add(set<int> a, set<int> b) { for (auto it = a.begin(); it != a.end(); ++it) b.insert(*it); return b; } int sq(int x) { return sqrt(x); } void dfs(int num, int mx) { if (mx > num) { used[mx][num] = used[num][num]; dp[mx][num] = dp[num][num]; } if (used[mx][num]) return; used[mx][num] = 1; for (int i = 1; i * i <= num; i++) { if (num % i) continue; if (i <= mx && i != 1) { dfs(num / i, i); dp[mx][num] = add(dp[mx][num], add(dp[i][num / i], i - 1)); } if (num / i <= mx && i != num / i) { dfs(i, num / i); dp[mx][num] = add(dp[mx][num], add(dp[num / i][i], num/i - 1)); } } } int main() { fastIO; cin >> n; used[1][1] = 1; dp[1][1].insert(1); for (int i = 2; i * i <= n; i++) { if (n % i) continue; if (i != 1) { dfs(n / i, i); ans = add(ans, add(dp[i][n / i],i-1)); } if (i != n / i) { dfs(i, n / i); ans = add(ans, add(dp[n / i][i], n/i - 1)); } } ans.insert(n); cout << ans.size() << endl; for (auto it = ans.begin(); it != ans.end(); ++it) cout << (*it)-1 << " "; cout << endl; return 0; } /* 3 1 2 1 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...