Submission #94421

#TimeUsernameProblemLanguageResultExecution timeMemory
94421Noam527Toys (CEOI18_toy)C++17
59 / 100
3407 ms263168 KiB
#include <bits/stdc++.h>
#define CHECK cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
using namespace std;

void debug(string names) {
	cout << '\n';
}
template<typename A1, typename... A2>
void debug(string names, A1 par, A2... left) {
	int pos = 0;
	for (; pos < names.size() && names[pos] != ' '  && names[pos] != ','; pos++)
		cout << names[pos];
	cout << ": " << par << "  ";
	while (pos < names.size() && (names[pos] == ' ' || names[pos] == ',')) {
		pos++;
	}
	names.erase(names.begin(), names.begin() + pos);
	debug(names, left...);
}

struct somn {
	int ind;
	ll left, sum;
	somn(int i, ll l, ll s) {
		ind = i, left = l, sum = s;
	}
	bool operator < (const somn &a) const {
		if (ind != a.ind) return ind < a.ind;
		if (left != a.left) return left < a.left;
		return sum < a.sum;
	}
};

ll n;
vector<ll> a;
set<ll> s;
set<somn> cache;

void calc(int ind, ll left, ll sum) {
	if (left == 1) {
		s.insert(sum);
		return;
	}
	if (ind == a.size() || left < a[ind]) return;
	if (cache.count(somn(ind, left, sum))) return;
	cache.insert(somn(ind, left, sum));
	calc(ind + 1, left, sum);
	while (left % a[ind] == 0) {
		left /= a[ind];
		sum += a[ind] - 1;
		calc(ind + 1, left, sum);
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);

	cin >> n;
	for (ll i = 2; i * i <= n; i++) {
		if (n % i == 0) {
			a.push_back(i);
			if (i != n / i) a.push_back(n / i);
		}
	}
	sort(a.begin(), a.end());
	a.push_back(n);
	calc(0, n, 0);
	cout << s.size() << '\n';
	for (auto &i : s) cout << i << " "; cout << '\n';
}

Compilation message (stderr)

toy.cpp: In function 'void calc(int, ll, ll)':
toy.cpp:48:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (ind == a.size() || left < a[ind]) return;
      ~~~~^~~~~~~~~~~
toy.cpp: In function 'int main()':
toy.cpp:73:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for (auto &i : s) cout << i << " "; cout << '\n';
  ^~~
toy.cpp:73:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (auto &i : s) cout << i << " "; cout << '\n';
                                      ^~~~
#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...