Submission #1196906

#TimeUsernameProblemLanguageResultExecution timeMemory
1196906LucaLucaMToys (CEOI18_toy)C++17
100 / 100
1978 ms86476 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <set>

using ll = long long;
#define debug(x) #x << " = " << x << '\n'

int main() {
  #ifdef LOCAL
    freopen("input.txt", "r", stdin);
  #endif
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(0);
  
  int n;
  std::cin >> n;

  std::vector<int> divs;
  for (int d = 1; d * d <= n; d++) {
    if (n % d == 0) {
      divs.push_back(d);
      if (d * d != n) {
        divs.push_back(n / d);
      }
    }
  }

  std::sort(divs.begin(), divs.end());

  int sz = (int) divs.size();
  std::vector<std::set<int>> sums(sz);
  
  sums[0].insert(0);
  for (int i = 1; i < sz; i++) {
    for (int j = 0; j < i; j++) {
      if (divs[i] % divs[j] == 0) {
        // sums[i] U= sums[j] + divs[i] / divs[j] - 1
        for (int k : sums[j]) {
          sums[i].insert(k + divs[i] / divs[j] - 1);
        }
      }
    }
  }
  
  std::cout << sums.back().size() << '\n';
  for (int x : sums.back()) {
    std::cout << x << ' ';
  }
  
  return 0;
}
#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...