제출 #1128735

#제출 시각아이디문제언어결과실행 시간메모리
1128735Alihan_8Toys (CEOI18_toy)C++20
39 / 100
5091 ms107056 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

vector <vector<int>> D(N);

signed main(){
	for ( int i = 2; i < N; i++ ){
		for ( int j = i; j < N; j += i ) D[j].push_back(i);
	}
	
	int n; cin >> n;
	
	if ( n == 1 ) return cout << "1\n0\n", 0;
	
	vector <int> d{n};
	
	for ( int i = 2; i * i <= n; i++ ){
		if ( n % i == 0 ){
			d.push_back(i);
			
			if ( i * i != n ) d.push_back(n / i);
		}
	}
	
	sort(d.begin(), d.end());
	
	vector <map<int,bool>> mp(n);
	
	auto dfs = [&](auto dfs, int s, int x) -> bool{
		if ( s == 0 && x == 1 ) return true;
		
		if ( mp[s].count(x) ) return mp[s][x];
		
		bool &ret = mp[s][x]; ret = 0;
		
		for ( auto &y: D[x] ){
			if ( y > s + 1 ) break;
			
			ret |= dfs(dfs, s + 1 - y, x / y);
		}
		
		return ret;
	};
	
	vector <int> ans;
	
	for ( int i = 1; i < n; i++ ){
		if ( dfs(dfs, i, n) ) ans.push_back(i);
	}
	
	cout << ans.size() << '\n';
	
	for ( auto &x: ans ) cout << x << ' ';
	
	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...