Codeforces_forever Round #1 (Div3) С

//решение
Для этой задачи существует два подхода к её решению.

Математическое решение

Заметим, что в ответе всегда будут присутствовать числа 0≤x<⌊n−−√⌋. В этом можно убедиться, решив уравнение ⌊nk⌋=x, эквивалентное неравенству x≤nk<x+1, для целых значений k. Решением двойного неравенства является промежуток k∈(nx+1;nx], длина которого равна nx2+x. При x<⌊n−−√⌋ nx2+x>1, а на промежутке длины большей, чем 1, всегда найдётся целое решение k=⌊nx⌋ ⟹ все целые числа 0≤x<⌊n−−√⌋ принадлежат ответу.

Теперь заметим, что нам больше не требуется перебирать значения k>⌊n−−√⌋, ведь этим числам всегда соответствуют значения 0≤x<⌊n−−√⌋. Таким образом, можно, как в наивном решении, перебрать все значения k до ⌊n−−√⌋ и добавить x=⌊nk⌋ к ответу. Остаётся только аккуратно обработать случай k=⌊n−−√⌋.

Асимптотика решения: O(n−−√logn) или O(n−−√)
Алгоритмическое решение

В задаче можно было предположить, что чисел в ответе не так уж и много (ведь их же всех ещё нужно вывести, на что тратится основное время выполнения программы). Очевидно, что n всегда принадлежит ответу. Заметим также, что при увеличении k значение x=⌊nk⌋ уменьшается. Таким образом, можно с помощью бинарного поиска находить такое наименьшее значение k′, что nk′<x. x′=nk′ и будет являться предыдущим для x в ответе на эту задачу.

Асимптотика решения: O(n−−√logn)
//реализация
#include <bits/stdc++.h>
#define ALL(s) (s).begin(), (s).end()
#define rALL(s) (s).rbegin(), (s).rend()
#define sz(s) (int)(s).size()
#define mkp make_pair
#define pb push_back
#define sqr(s) ((s) * (s))

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef unsigned int ui;

#ifdef EUGENE
	mt19937 rng(1337);
#else
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#endif

void solve() {
	int n;
	cin >> n;
	vector<int> ans;
	int s = (int)sqrtl(n);
	for (int i = 0; i <= s; i++)
		ans.pb(i);
	for (int i = 1; i <= s; i++)
		ans.pb(n / i);
	sort(ALL(ans));
	ans.resize(unique(ALL(ans)) - ans.begin());
	cout << sz(ans) << endl;
	for (int &x : ans)
		cout << x << " ";
	cout << endl;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);
	#ifdef EUGENE
		freopen("input.txt", "r", stdin);
		// freopen("output.txt", "r", stdout);
	#endif

	int t;
	cin >> t;
	while (t--)
		solve();
}