题解：P12541 [APIO2025] Hack!
luogu_gza
·
·
题解
首先感谢 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>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**。