Submission #1228986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228986		radodododo	Toys (CEOI18_toy)	C++20	39 / 100	5092 ms	460 KiB

toy

#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> chs;
vector<vector<long long>> step;

void f(long long i, long long m, long long pos) {
	if (pos == summa - 1) {
		chs[pos] *= step[i][m];
		if (i + 1 < prs.size()) {
			f(i + 1, much[i + 1], 0);
			chs[pos] /= step[i][m];
		}
		else {
			long long r = 0;
			for (auto chch : chs) {
				r += chch - 1;
			}
			ans.insert(r);
			chs[pos] /= step[i][m];
		}
	}
	else {
		for (long long sta = 0; sta <= m; sta++) {
			chs[pos] *= step[i][sta];
			f(i, m - sta, pos + 1);
			chs[pos] /= step[i][sta];
		}
	}
}

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;
	}
	chs.resize(summa, 1);
	step.resize(prs.size(), vector<long long>(summa + 1, 1));
	for (long long i = 0; i < prs.size(); i++) {
		for (long long j = 1; j <= much[i]; j++) {
			step[i][j] = step[i][j - 1] * prs[i];
		}
	}
	f(0, much[0], 0);
	cout << ans.size() << '\n';
	for (auto as : ans) {
		cout << as << " ";
	}
}

• Subtask 1: 19 / 19
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 21