C
https://codeforces.com/gym/103118/problem/C
题面：
在猫的国度里，任何猫科动物都可以被视为一棵根深蒂固的树。众所周知，猫的体内都隐藏着一种僵尸病毒。因此，一个猫家庭可能由猫和僵尸组成。当一只猫出生时，它可能会变成僵尸。如果一只猫变成了僵尸，它的后代也会变成僵尸。
现在给定一个整数 \(K\) ，你应该用恰好 \(K\) 种方法来构建一个猫科家族，以标记家族成员的身份(猫或僵尸)。当且仅当至少有一个成员在一种方式中被标记为猫，而在另一种方式中被标记为僵尸时，两种方式才被认为是不同的。
从形式上看，有根树中的顶点会被标记为黑色或白色，如果一个顶点被标记为黑色，那么其子树中的所有顶点也应该被标记为黑色。给定一棵有根树，很容易计算出在树上标记顶点的有效方法的数量。你的任务是构建一棵有根的树，用恰好 \(K\) 种方法标记树中的顶点。当且仅当至少有一个顶点在一种标记方式中被标记为黑色，而在另一种标记方式中被标记为白色时，两种标记方式才会被认为是不同的。
输入
唯一一行包含一个整数 \(K\) - 树中顶点的有效标记方式的数量。 \((2 \le K \le 2 \cdot 10^{18})\) - 树中顶点的有效标记方式的数量。
输出
我们用 \(n\) 表示您构建的树的顶点数，并标注从 \(1\) 到 \(n\) 的顶点，其中顶点 \(1\) 是根。
输出结果应包含 \(n\) 行。在第一行中，打印一个整数 \(n\) \((1 \le n \le 10^5)\) 。在接下来的每 \(n-1\) 行中，打印两个整数 \(u,v\) \((1 \le u, v \le n, u \neq v)\) 描述一个根。 \((1 \le u, v \le n, u \neq v)\) 描述有根树的一条边。
保证至少存在一个解决方案。如果存在多个可能的有效解，则可以打印任意一个。
从简单的开始分析,一个点有两种方案数 (1/0),此时他的父节点一定是0，如果他的父节点是1，那么他也只能是1。所以相比单个节点，给他增加一个父节点可以让方案数x+1。如果两个点不是父子关系(不互相影响)，那么他们的方案数是\(2*2\),但是所有的点要相互连通，就必须再加一个点当他们的父节点，此时的方案数变化是\(x*2+1\)。
那么现在有两种变化方法，一种是让方案数+1,一种是让方案数*2之后再+1。最开始的方案数是2，那么从2开始可以一步步变成n 。同等于从n变化成2,可以-1或者-1之后/2，因为方案数只有正整数，所以偶数只能-1，奇数则执行-1后/2.如果算到3，则不需要除2直接结束。要注意计算的方案和建树是反过来的。
代码如下：
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve()
{
int n;
cin >> n;
vector<int> v;
while (n > 2)
{
if (n % 2 == 0)
{
n --;
v.push_back(0);
}
else
{
if ((n - 1) / 2 >= 2)
{
n = (n - 1) / 2;
v.push_back(1);
}
else
{
n --;
v.push_back(0);
}
}
}
int up = 1;
vector<pair<int, int>> g;
reverse(v.begin(), v.end());
for (auto x : v)
{
if (x)
{
g.push_back({up, up + 2});
g.push_back({up + 1, up + 2});
up += 2;
}
else
{
g.push_back({up, up + 1});
up ++;
}
}
cout << up << "\n";
reverse(g.begin(), g.end());
for (auto [x, y] : g)
cout << up - y + 1 << ' ' << up - x + 1 << "\n";
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
}