Submission #299538

#	Time	Username	Problem	Language	Result	Execution time	Memory
299538		Berted	Toys (CEOI18_toy)	C++14	100 / 100	2028 ms	19916 KiB

toy

#include <iostream>
#include <algorithm>
using namespace std;

int n, ans[10000001], size, sum; 

void DFS(int n, int p)
{
	//cout << "DFS " << n << " " << p << "\n";
	if (n == 1) 
	{
		ans[size++] = sum;
	}
	else
	{
		for (int i = 1; i * i <= n; i++)
		{
			if (n % i == 0)
			{
				if (i <= p && i > 1)
				{
					sum += i - 1;
					DFS(n / i, i);
					sum -= i - 1;
				}
				if (n / i <= p)
				{
					sum += n / i - 1;
					DFS(i, n / i);
					sum -= n / i - 1;
				}
			}
		}
	}
}

int main()
{
	ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	DFS(n, 1000000000);

	sort(ans, ans + size);
	size = unique(ans, ans + size) - ans;

	cout << size << "\n";
	for (int i = 0; i < size; i++)
	{
		cout << ans[i];
		if (i + 1 < size) cout << " ";
	}
	cout << "\n";

	return 0;
}

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