自动搬运

查看原文

来自洛谷，原作者为

	luogu_gza 猫猫怎么这么可爱

搬运于2025-08-24 23:16:20，当前版本为作者最后更新于2025-05-21 10:37:59，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

首先感谢 milmon 老师提示，我才能摸索出更好的做法。

考场上冲击 T1，毁我大好青春，只得 77 分。

首先先讲一下怎么判定 $[l,r]$ 中有没有 $n$ 的倍数（note：返回值是否为零等价于序列中数字两两相减，能不能减出 $n$ 的倍数）

取 $C=\sqrt{r-l+1}$，构造序列 $[1,2,\cdots,C,l+C,l+2C,\cdots,r+1]$，根据其返回值是否为零即可判定 $[l,r]$ 中有没有 $n$ 的倍数。注意这里需要保证 $l=1$ 或者 $n>C$ 这个构造才是对的，因为要防止 $1 \sim C$ 这一段能减出来在 $[l,r]$ 之外的 $n$ 的倍数导致误判。

update：讲一下问什么这是对的。我们称第一部分为 $[1,2,\cdots,C]$，其他的为第二部分。首先第一部分内部没有贡献，第一部分和第二部分互相产生的贡献恰好判断 $[l,r]$ 有没有 $n$ 的倍数。

接下来就是要证明第二部分内部贡献不会影响判断。我们把第二部分想象成一个指针在一个长度为 $n$ 的环上走，$1 \sim C$ 已经被标记了，走一步将指针往后动 $C$ 格。如果这个指针走到了被标记的地方就会对返回值产生贡献，或者走到了一个地方两次也会对返回值产生贡献。

你发现标记区间长度为 $C$，所以你在这个环上走一圈，一定会走到这上面，使得返回值不为零，因为如果第二部分内部产生了贡献（走了一圈），一定会使得第一部分和第二部分互相产生贡献，所以这是对的。

我们先判一下 $n \leq B$ 还是 $n>B$。

$n \leq B$：直接判。

$n>B$：二分答案，每次判定 $[l,mid]$ 中含不含有 $n$ 的倍数然后动一下边界就行。

以上的做法能做到 $77 \sim 78$ 分，也是我考场做法。

我们考虑如果 $n<5 \times 10^8$，那么它一定有一个在 $[5 \times 10^8,1 \times 10^9]$ 之间的倍数，直接将二分初始边界改为 $[5 \times 10^8,1 \times 10^9]$，然后你能算出一个 $n$ 的倍数，枚举其因数然后找出真正的 $n$ 即可。

这样貌似只能获得 99 分，再加一个剪枝，因为我们已经保证了 $n>B$，所以算出来的 $n$ 的倍数的因数中，$\leq B$ 的一定不会是答案，判的时候跳过这些数就行。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
int hack();
long long collisions(std::vector<long long> x);
#define fo(i,a,b) for(long long i=a;i<=b;i++)
long long get(long long l,long long r)
{
	int C=sqrt(r-l+1);
	vector<long long> v;
	fo(i,1,C) v.pb(i);
	l+=C;
	while(l<=r) v.pb(l),l+=C;
	v.pb(r+1);
	return collisions(v);
}
int hack()
{
	long long B=sqrt(1e9),v=get(1,B);
	if(v)
	{
		fo(i,1,B) if(collisions({1,i+1})) return i;
		return -1;
	}
	else
	{
		long long l=5e8,r=1e9;
		while(l<r)
		{
			long long mid=l+r>>1;
			if(get(l,mid)) r=mid;
			else l=mid+1;
		}
		vector<long long> v;
		for(long long i=1;i*i<=l;i++) if(l%i==0)
		{
			if(i>B) v.pb(i);
			if(i*i!=l&&l/i>B) v.pb(l/i);
		}
		sort(v.begin(),v.end());
		for(auto i:v) if(collisions({1,i+1})) return i;
		return -1;	
	}
}

然后我们尝试结合一下 @yuanruiqi 题解的做法。

询问的时候把每个数乘上 $2^{29}$，这样你就只需要二分奇数即可，也就是你会得到一个 $n$ 的倍数去除了所有 $2$ 因子的结果，把它乘上 $2^{29}$，枚举其所有质因数，二分 $n$ 有几个枚举的质因子因子即可。

以及你其实根本不用判 $n<\sqrt{10^9}$。为什么呢？

因为长度大于等于 $n$ 的区间内一定存在 $n$ 的倍数，所以你的二分区间会一直缩小到至少 $[l,l+2n)$（此处的 $l$ 是初始二分左端点），而在 $n \geq 2$ 时，此时已经满足 $n<C=\sqrt{2n}$ 了，因此接下来再跑这个算法就是对的。

值得注意的是，为了防止询问的数超出 $10^{18}$，我们需要将二分的下界调低一点，我这里是调了 $10^9 \div 6$ 左右。

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
// #include"hack.h" 
int hack();
long long collisions(std::vector<long long> x);
#define fo(i,a,b) for(long long i=a;i<=b;i++)
long long get(long long l,long long r)
{
	int C=ceil(sqrt(r-l+1));
	vector<long long> v;
	fo(i,1,C) v.pb(i);
	l+=C;
	while(l<=r) v.pb(l),l+=C;
	v.pb(r+1);
	return collisions(v);
}
long long get2(long long l,long long r)
{
	int C=sqrt(r-l+1);
	vector<long long> v;
	fo(i,1,C) v.pb((2ll*i)<<29);
	l+=C;
	for(;;l+=C)
	{
		l=min(l,r+1),v.pb((l*2ll-1)<<29);
		if(l-1>=r) break;
	}
	return collisions(v);
}
long long qmi(long long a,long long b)
{
	long long res=1;
	fo(i,1,b) res*=a;
	return res;
}
int hack()
{
	long long B=sqrt(1e9);
	long long l=1e9/6+1,r=5e8;
	while(l<r)
	{
		long long mid=l+r>>1;
		if(get2(l,mid)) r=mid;
		else l=mid+1;
	}
	l=l*2-1;
	l<<=29;
	vector<long long> v;
	long long now=l;
	for(long long i=2;i*i<=l;i++) if(l%i==0)
	{
		long long ori=l;
		long long cnt=0;
		while(l%i==0) l/=i,cnt++;
		long long ll=0,rr=cnt;
		while(ll<rr)
		{
			long long mid=ll+rr+1>>1;
			if(collisions({1,now/qmi(i,mid)+1})) ll=mid;
			else rr=mid-1;
		}
		now/=qmi(i,ll);
		// cout<<now<<endl;
	}
	if(l>1)
	{
		if(collisions({1,now/l+1})) now/=l;
	}
	return now;
}

次数：88186。