[APIO2025] Hack!

· · 题解

题意大概是根据冲突次数问出来哈希模数。

实际上，本题中无需知道冲突次数，只需知道是否冲突。

考虑集合 S 冲突的充要条件，可以发现就是看是否存在两个数 x\in S,y\in S，且 x\equiv y\pmod n。

也就是是否存在两个数 x\in S,y\in S，且 n|x-y。

如果我们能构造出一个集合，使得所有能表示成这个集合中两数之差的数构成一个前缀，那么就可以通过二分答案求出 n。

问题转化为对于给定的 m 求出一个集合 S，使得存在 x\in S,y\in S，满足 k=x-y 当且仅当 k\le m。

一种经典的构造是取 T=\sqrt m，取 S=\{1,2,3,\dots,T,T+1,2T+1,3T+1,\dots,m+1\}。

这样总共需要 2\sqrt m 个数，总复杂度 O(\sqrt n\log n)，只有 25 分。

考虑优化。

这个做法的问题在于当我们二分的区间很小的时候，如果 l,r 都很大，那么集合的大小比较大。

考虑能否构造一个大小与区间长度相关的集合，从而查询这个区间内是否有 n 的倍数。

令 T=\sqrt {r-l+1}，构造 S=\{1,2,3,\dots,T,l+T,l+2T,\dots,r+1\}。

于是，我们的查询次数为 \sum\limits_{2^i\le n}\sqrt\frac{n}{2^i}=O(\sqrt n)。

但是由于常数很大，无法通过。

注意到，由于 n\le 10^9，所以一定存在一个 n 的倍数大于 5\times 10^8。

于是把初始二分区间设置为 [5\times 10^8,10^9]，二分出来一个结果 N，枚举 N 的因数，逐个检测是否是答案即可。

这样可以获得神秘的 99 分。

最后一个优化是可以直接试除 N 的质因子，对于质因子 p，如果 \frac Np 依然是 n 的倍数就把 N 除去 p，这样最后一部分复杂度 O(\log n)，可以通过。

#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;
}