제출 #331445

#제출 시각아이디문제언어결과실행 시간메모리
331445davitmargToys (CEOI18_toy)C++17
0 / 100
8 ms9728 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 = 1; i * i <= n; i++) { if (n % i) continue; int P = i; for (int j = 1; j * j <= n / P && j <= P; j++) { if ((n / P) % j) continue; int p = j; if (p != 1) { dfs(n / P / p, p); ans = add(ans, add(dp[P][n / P / p], P + p - 2)); } p = n / P / p; dfs(n / P / p, p); ans = add(ans, add(dp[P][n / P / p], P + p - 2)); } P = n / P; for (int j = 1; j * j <= n / P && j <= P; j++) { if ((n / P) % j) continue; int p = j; if (p != 1) { dfs(n / P / p, p); ans = add(ans, add(dp[P][n / P / p], P + p - 2)); } p = n / P / p; dfs(n / P / p, p); ans = add(ans, add(dp[P][n / P / p], P + p - 2)); } } 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...