题解：P12541 [APIO2025] Hack!

首先感谢 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$ ，所以你在这个环上走一圈，一定会走到这上面，使得返回值不为零，因为如果第二部分内部产生了贡献（走了一圈），一定会使得第一部分和第二部分互相产生贡献，所以这是对的。

取

B=\sqrt n

，我们先判一下

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

的一定不会是答案，判的时候跳过这些数就行。

CPP

#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

左右。

CPP

#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。

题解：P12541 [APIO2025] Hack!

文章操作

相关推荐

评论

题解：P12541 [APIO2025] Hack!