自动搬运

查看原文

来自洛谷，原作者为

	weifengzhaomi 加油，不要辜负对朱前泰说的话

搬运于2025-08-24 23:14:03，当前版本为作者最后更新于2025-05-09 23:04:26，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目意思已经很详细，这里不在复述。

思路

由于 $n$ 的范围很大，如果每次询问都 $O(n)$ 查找就是 $O(tn)$ 的复杂度，肯定是不能过的，所以考虑预处理。

先设一个 $a$ 数组，用于存储答案。

然后，设置两个数组，$l$ 和 $r$，含义与题目相同。

接着，按照题目来模拟 $5$ 个特征。

• $l_1 = 1$。
• $l_i \le r_i$。
• $r_i - l_i \ge k$。
• $\gcd(l_i,r_i) = 1$。
• $r_i - l_i$ 尽可能小。

更多细节见代码。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int cnt[5000010],l[5000010],r[5000010],k,t,n,top = 1;
signed main(){
	scanf("%lld",&k);
	while (true){
		l[top] = r[top - 1] + 1,r[top] = l[top] + k;
		while (__gcd(l[top],r[top]) != 1) r[top]++;
		for (int i = l[top];i <= r[top];i++) cnt[i] = top;
		if (r[top] >= 1000000) break;
		top++;
	}
	scanf("%lld",&t);
	while(t--) scanf("%lld",&n),printf("%lld\n",cnt[n]);
}