Submission #490977

#	Time	Username	Problem	Language	Result	Execution time	Memory
490977		hollwo_pelw	Toys (CEOI18_toy)	C++17	100 / 100	3702 ms	4844 KiB

toy

#include <bits/stdc++.h>
using namespace std;

vector<int> d;
set<int> res;

inline int getpos(int a) {
    return lower_bound(d.begin(), d.end(), a) - d.begin();
}

void backtrack(int val, int cur, int sum = 0) {
    if (val == 1)
        return res.insert(sum), (void) 0;
    if (cur == d.size()) return ;
    
    int x = d[cur];
    
    if (val < x) return ;
    if (val == x)
        return backtrack(val / x, cur + 1, sum + x - 1);
    
    backtrack(val, cur + 1, sum);
    while (val % x == 0) {
        val /= x, sum += x - 1;
        backtrack(val, cur + 1, sum);
    }
}

signed main() {
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
	int n; cin >> n;
	for (int i = 2; i * i <= n; i++) {
	    if (n % i == 0) {
	        d.push_back(i);
	        if (n / i != i)
	            d.push_back(n / i);
	    }
	}
	sort(d.begin(), d.end());
	
	backtrack(n, 0);
	
	res.insert(n - 1);
	
	cout << res.size() << '\n';
	for (auto v : res)
	    cout << v << ' ';
}

Compilation message (stderr)

toy.cpp: In function 'void backtrack(int, int, int)':
toy.cpp:14:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     if (cur == d.size()) return ;
      |         ~~~~^~~~~~~~~~~

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