/
1469d.cpp
66 lines (63 loc) · 1.58 KB
/
1469d.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
* author: vishnus
* created: 2022-08-17
**/
#include <bits/stdc++.h>
using namespace std;
// Idea: we know that most of the numbers will directly have to be set to 1. So which numbers should
// we set to 2 then 1? Well, take the largest number, and find the smallest number such that dividing
// the largest by it twice gives 1. This will be ceil(sqrt(largest number)). We can do this recursively.
// It will be n + log(log(n)). Why? Because continual sqrts (like 2^16, 2^8, 2^4, etc.) has the exponent
// itself decreasing by log.
int main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(false);
cin.tie(0);
#endif
int tt;
cin >> tt;
while (tt--) {
int n;
cin >> n;
vector<pair<int, int>> steps;
#ifndef ONLINE_JUDGE
vector<int> test(n);
for (int i = 0; i < n; i++) {
test[i] = i + 1;
}
#endif
function<void(int)> Solve = [&](int R) {
if (R == 2) {
return;
}
int nxt = ceil(sqrt(R));
for (int i = nxt + 1; i < R; i++) {
steps.push_back({i, R});
#ifndef ONLINE_JUDGE
test[i - 1] = 1;
#endif
}
steps.push_back({R, nxt});
steps.push_back({R, nxt});
#ifndef ONLINE_JUDGE
test[R - 1] = 1;
#endif
Solve(nxt);
};
Solve(n);
#ifndef ONLINE_JUDGE
assert((int) steps.size() <= n + 5);
int ocnt = 0, tcnt = 0;
for (int i = 0; i < n; i++) {
ocnt += (test[i] == 1);
tcnt += (test[i] == 2);
}
assert(ocnt == n - 1);
assert(tcnt == 1);
#endif
cout << steps.size() << '\n';
for (auto [x, y] : steps) {
cout << x << ' ' << y << '\n';
}
}
}