自动搬运

查看原文

来自洛谷，原作者为

	Flanksy Where we gonna go?

搬运于2025-08-24 22:41:22，当前版本为作者最后更新于2023-11-10 21:22:52，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

数学

很难想的分类讨论，笔者的思路中只有一种能够得到答案。

$n \leq 1000000$

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

$n \leq 3793540542$

利用得到的信息扩展可以求解的范围，发现 $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$ 时任意 $G_n$ 的值。

$3793540543 \leq n \leq 2 \times 10^{15}$

进一步扩展，如果区间 $[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 \frac{n-l'+1}{i} \right \rceil -1 = l+ \left \lfloor \frac{n-l'}{i} \right \rfloor$。

结合 $n \leq 3793540542$ 时的做法能够通过本题。

#include<bits/stdc++.h>
using namespace std;
constexpr long long uim=3793540542ll;
constexpr int sta=6138,lim=1000147;
int pos,dp[2000005];//dp[i]存储数列第i项的值  
long long n,ans;
int main(){
	scanf("%lld",&n);
	pos=3,dp[1]=1ll,dp[2]=2ll,dp[3]=2ll;
	for(int i=3;pos+1<=lim;i++)
		for(int j=1;j<=dp[i]&&pos+1<=lim;j++){
			dp[++pos]=i;
			if(pos==n) return printf("%d\n",i),0;
		}
	long long l=lim,r=lim,ls=uim,rs=uim;
	for(int i=sta;i<=lim;i++){
		l=r+1,r+=dp[i];					//更新j的范围 
		ls=rs+1,rs+=(r-l+1)*i;			//更新k的范围 
		if(n>=l&&n<=r) ans=i;			//找到答案(n<=3793540542)
		if(n>=ls&&n<=rs) ans=l+(n-ls)/i;//找到答案(n>=3793540543)
		if(ans!=0ll) break;
	}
	printf("%lld\n",ans);
	return 0;
}