专栏文章

[APIO2025] Hack!

__ANIG_
P12541题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip8wca1
此快照首次捕获于
2025/12/03 08:04
3 个月前
此快照最后确认于
2025/12/03 08:04
3 个月前
查看原文
题意大概是根据冲突次数问出来哈希模数。
实际上，本题中无需知道冲突次数，只需知道是否冲突。
考虑集合 SS 冲突的充要条件，可以发现就是看是否存在两个数 x∈S,y∈Sx\in S,y\in S，且 x≡y(modn)x\equiv y\pmod n。
也就是是否存在两个数 x∈S,y∈Sx\in S,y\in S，且 n∣x−yn|x-y。
如果我们能构造出一个集合，使得所有能表示成这个集合中两数之差的数构成一个前缀，那么就可以通过二分答案求出 nn。
问题转化为对于给定的 mm 求出一个集合 SS，使得存在 x∈S,y∈Sx\in S,y\in S，满足 k=x−yk=x-y 当且仅当 k≤mk\le m。
一种经典的构造是取 T=mT=\sqrt m，取 S={1,2,3,…,T,T+1,2T+1,3T+1,…,m+1}S=\{1,2,3,\dots,T,T+1,2T+1,3T+1,\dots,m+1\}。
这样总共需要 2m2\sqrt m 个数，总复杂度 O(nlog⁡n)O(\sqrt n\log n)，只有 2525 分。
考虑优化。
这个做法的问题在于当我们二分的区间很小的时候，如果 l,rl,r 都很大，那么集合的大小比较大。
考虑能否构造一个大小与区间长度相关的集合，从而查询这个区间内是否有 nn 的倍数。
令 T=r−l+1T=\sqrt {r-l+1}，构造 S={1,2,3,…,T,l+T,l+2T,…,r+1}S=\{1,2,3,\dots,T,l+T,l+2T,\dots,r+1\}。
于是，我们的查询次数为 ∑2i≤nn2i=O(n)\sum\limits_{2^i\le n}\sqrt\frac{n}{2^i}=O(\sqrt n)。
但是由于常数很大，无法通过。
注意到，由于 n≤109n\le 10^9，所以一定存在一个 nn 的倍数大于 5×1085\times 10^8。
于是把初始二分区间设置为 [5×108,109][5\times 10^8,10^9]，二分出来一个结果 NN，枚举 NN 的因数，逐个检测是否是答案即可。
这样可以获得神秘的 9999 分。
最后一个优化是可以直接试除 NN 的质因子，对于质因子 pp，如果 Np\frac Np 依然是 nn 的倍数就把 NN 除去 pp，这样最后一部分复杂度 O(log⁡n)O(\log n)，可以通过。
CPP
#include <bits/stdc++.h>
using namespace std;
#define int long long
int collisions(vector<int>q);
bool chk(int l,int r){
	int y=sqrt(r-l)+1;
	vector<int>q;
	for(int i=1;i<=y;i++)q.push_back(i);
	for(int i=y+l;i<=r;i+=y)q.push_back(i);
	q.push_back(r+1);
	return collisions(q);
}
signed hack(){
	int l=5e8+1,r=1e9;
	while(l<r){
		int mid=l+r>>1;
		if(chk(l,mid))r=mid;
		else l=mid+1;
	}
	for(int i=2;i*i<=l;i++){
		if(l%i==0){
			while(l%i==0)l/=i;
			while(r%i==0&&r!=i&&collisions({1,r/i+1}))r/=i;
		}
	}
	while(l>1&&r%l==0&&r!=l&&collisions({1,r/l+1}))r/=l;
	return r;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...