Submission #1229039

#TimeUsernameProblemLanguageResultExecution timeMemory
1229039radodododoToys (CEOI18_toy)C++20
100 / 100
4099 ms4536 KiB
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

long long summa = 0;
vector<long long> prs, much;
set<long long> ans;
vector<long long> dels;
long long ss = 0;

void f(long long pos, long long m, long long limi) {
	if (pos == summa - 1) {
		ss += m;
		ans.insert(ss - summa);
		ss -= m;
	}
	else {
		for (long long gh = 0; gh <= limi; gh++) {
			if (m % dels[gh] == 0) {
				ss += dels[gh];
				f(pos + 1, m / dels[gh], gh);
				ss -= dels[gh];
			}
		}
	}
}

int main() {
	long long n;
	cin >> n;
	if (n == 1) {
		cout << 1 << '\n' << 0;
		return 0;
	}
	long long lim = 1e5;
	vector<bool> prost(lim, 1);
	long long nn = n;
	for (long long i = 2; i < lim; i++) {
		if (prost[i]) {
			if (n % i == 0) {
				prs.push_back(i);
				long long muc = 0;
				while (nn % i == 0) {
					muc++;
					nn /= i;
				}
				much.push_back(muc);
			}
			for (long long j = i * i; j < lim; j += i) {
				prost[j] = 0;
			}
		}
	}
	if (nn > 1) {
		prs.push_back(nn);
		much.push_back(1);
	}
	for (auto z : much) {
		summa += z;
	}
	vector<long long> dd;
	for (long long i = 1; i * i <= n; i++) {
		if (n % i == 0) {
			dels.push_back(i);
			if (n / i != i) {
				dd.push_back(n / i);
			}
		}
	}
	for (long long gh = dd.size() - 1; gh >= 0; gh--) {
		dels.push_back(dd[gh]);
	}
	f(0, n, dels.size() - 1);
	cout << ans.size() << '\n';
	for (auto as : ans) {
		cout << as << " ";
	}
}
#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...