数学、自描述序列

暴力计算 $G_1,G_2,G_3 \cdots G_{10^6}$ 的值，计算完毕后可以回答 $n \leq 10^6$ 的询问。

利用得到的信息扩展可以求解的范围，发现 $G_{10^6}=6137,G_{6137}=264$，但 $6137$ 在序列前 $10^6$ 项中只出现 $117$ 次，扩展时需要考虑未出现的 $147$ 个 $6137$ 造成的影响。为了方便，计算 $G_1,G_2,G_3 \cdots G_{10^6+147}$，从 $G_{10^6+147+1}$，即 $G_{1000148}=6138$ 开始扩展。

由 $G_{6138}=264$ 得 $\forall \ i \in [10^6+147+1,10^6+147+264],G_i=6138$。枚举 $[6138,10^6+147]$ 中每个整数 $i$ 并计算满足 $G_j=i$ 的整数 $j$ 的范围能够回答 $n \leq 3793540542$ 时的询问。

进一步扩展，如果区间 $[l,r]$ 满足 $\forall \ j \in [l,r],G_j=i$，那么 $[l,r]$ 中的数在 $G$ 中将出现 $(r-l+1) \times i$ 次。满足 $G_j=i$ 的整数 $j$ 必定为一段连续自然数。利用以上性质确定 $G_n$ 的值域 $[l,r]$，该区间不仅需要满足 $\forall \ j \in [l,r],G_j=i$，还需要满足 $G_{l-1} \neq G_l,G_{r+1} \neq G_r$。

确定 $G_n$ 值域 $[l,r]$ 的同时可以确定满足 $G_k \in [l,r]$ 的整数 $k$ 的范围 $[l',r']$，显然 $n \in [l',r']$。根据自描述序列的定义，由于 $\forall \ j \in [l,r],G_j=i$，值域 $[l,r]$ 中的每个数在 $G$ 中都出现 $i$ 次。根据 $n$ 在区间 $[l',r']$ 中第 $n-l'+1$ 个位置得到 $G_n=l +\left \lceil \dfrac{n-l'+1}{i} \right \rceil -1 = l+ \left \lfloor \dfrac{n-l'}{i} \right \rfloor$。

将三种做法结合后可以通过本题。