great thanks to @Milmon and GPT-5.6 sol。
算法一
考场上冲击 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$ 的一定不会是答案，判的时候跳过这些数就行。
#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}$ 了，因此接下来再跑这个算法就是对的。
我们目标是在区间中找到一个和 $2$ 互质的 $n$ 的倍数，所以 $5 \times 10^8$ 需要调低一点，要调为 $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。
算法三
大家好，现在是 2026.8.27，我还是没有放过这个题。
叠个甲，下文的内容有一些是 gpt 教我的。
前置工作
我们记答案 $n=m2^a3^b$，其中 $\gcd(m,6)=1$。
首先我们把上文的 $[5 \times 10^8,1 \times 10^9]$ 改成 $[2 \times 10^8,1 \times 10^9]$，因为我们目标是在区间中找到一个和 $6$ 互质的 $m$ 的倍数，所以要稍微调低一点，具体为什么 $2 \times 10^8$ 可行，这里贴一个 g 老师的证明。
::::info[prove] 正确的最小通用下界是 $10^9/5$。对任意 $m\le 10^9$ 且 $\gcd(m,6)=1$：
- 若 $m\ge2\times10^8$，直接取 $m$；
- 否则令 $q$ 是最小的满足 $qm\ge2\times10^8$ 且 $\gcd(q,6)=1$ 的正整数。
与 6 互质的正整数从 $1,5,7,11,13,\ldots$ 开始，相邻两项之比不超过 5。设 $q$ 的前一项为 $q'$，则
$$ qm\le5q'm<10^9. $$
所以 $[2\times10^8,10^9]$ 中一定存在一个与 $6$ 互质的 $m$ 的倍数。下文只在这个必要的更大区间内搜索。 ::::
其实这个做法很久以前小豹子就提示过我，奈何我比较愚笨，今天看到了 @SnowTrace 老师的题解才反应过来。
直接按照 88186 次的做法去除 $2$ 和 $3$ 因子是不行的，我们需要上一些魔法。
定义新运算 $v \cdot \{a_1,a_2,\cdots,a_l\}=\{va_1,va_2,\cdots,va_l\}$，询问 $P \cdot \{1,2,\cdots,C,C+1,2C+1,\cdots,R+1\}$ 就可以判定 $\frac{n}{\gcd(n,P)}$ 是否 $\leq R$。
依次询问 $P=2^{14}$ 和 $P=3^{10}$，都令 $R=\lfloor \frac{10^9}{P} \rfloor$。
若某次返回非零，就对前缀二分，直接得到 $d=n/\gcd(n,P)$，于是 $Pd$ 已经是 $n$ 的倍数，可以直接将 $Pd$ 质因数分解，二分出 $n$ 在每个质因子上的次数即可。
若两次都为零，则必有 $a<14,b<10$，此时我们用给每个元素乘上 $S=2^{14} \times 3^{10}=967458816<10^9$，就不会出现询问数超过 $10^{18}$ 的问题了！
主判定
只二分与 $6$ 互质的数在实现上还是有点大大的问题的，这里采用一种取巧的方法，发现与 $6$ 互质的数只可能是 $6k+1$ 和 $6k+5$。
假设我们现在要判定从第 $L$ 块开始的若干完整块。选择一个只含 $2$ 和 $3$ 的数 $d$，令 $C=6d$，我们在第一部分放入 $[1,C]$ 中模 6 为 $0,2$ 的数，第二部分放入 $6L+1+C,\ 6L+1+2C,\ \ldots,\ 6L+1+qC$。
第二部分的每个数模 $6$ 都为 $1$。它减去第一部分，恰好覆盖前 $qd$ 个块中所有模 $6$ 为 $1,5$ 的数，没有覆盖别的数。
令 $H$ 为块数，那么 collision 中传入的元素个数为 $2d+\lfloor \frac Hd \rfloor$，取遍所有的 $d$ 选一个传入元素个数最小的即可。
最后只剩一个块，再用一次询问区分 $6k+1$ 与 $6k+5$。
排除较小的 $m$
由于主判定部分的构造较为奇怪，因此我们在做主判定之前需要排除一下较小的 $m$ 防止每部分内部撞车。
我们用【前置工作】中的办法询问 $P=S,R=34992=2^4 \times 3^7$。这个值大于等于主判定中我们会使用到的最大 $C$。
若返回非零，二分得到 $m$，并用 $Sm$ 还原答案。否则我们就得到了 $m>R$，排除了排除主询问两部分各自内部发生碰撞的可能。
代码
这么大一坨我怎么想写？贴一个 gpt 的。
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <limits>
#include <utility>
#include <vector>
int hack();
long long collisions(std::vector<long long> x);
namespace {
using int64 = long long;
constexpr int64 LIMIT_N = 1000000000LL;
constexpr int64 SMALL_M = 34992;
constexpr int64 POW2 = 1LL << 14;
constexpr int64 POW3 = 59049; // 3^10
constexpr int64 SCALE = POW2 * POW3;
int64 scaled(int64 x, int64 scale) {
return x * scale;
}
// Tests whether n / gcd(n, scale) is at most r.
bool prefix_has_multiple(int64 r, int64 scale) {
int64 c = static_cast<int64>(std::sqrt(static_cast<long double>(r)));
while (c * c < r) ++c;
while (c > 1 && (c - 1) * (c - 1) >= r) --c;
std::vector<int64> query;
query.reserve(static_cast<std::size_t>(c + r / c + 2));
for (int64 i = 1; i <= c; ++i) query.push_back(scaled(i, scale));
for (int64 x = c + 1; x <= r; x += c) {
query.push_back(scaled(x, scale));
}
query.push_back(scaled(r + 1, scale));
return collisions(std::move(query)) != 0;
}
// Precondition: prefix_has_multiple(limit, scale) is true.
int64 find_effective_modulus(int64 limit, int64 scale) {
int64 low = 1, high = limit;
while (low < high) {
const int64 mid = (low + high) / 2;
if (prefix_has_multiple(mid, scale)) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
std::vector<int64> smooth_steps() {
std::vector<int64> result;
for (int64 p2 = 1; p2 <= SMALL_M / 6; p2 *= 2) {
for (int64 d = p2; d <= SMALL_M / 6; d *= 3) {
result.push_back(d);
if (d > SMALL_M / 18) break;
}
}
std::sort(result.begin(), result.end());
result.erase(std::unique(result.begin(), result.end()), result.end());
return result;
}
struct Step {
int64 d;
int64 groups;
};
Step choose_step(int64 half, const std::vector<int64>& steps) {
Step best{0, 0};
int64 best_cost = std::numeric_limits<int64>::max();
for (int64 d : steps) {
if (d > half) break;
const int64 groups = half / d;
if (groups >= SMALL_M) continue;
const int64 cost = 2 * d + groups;
if (cost < best_cost) {
best_cost = cost;
best = {d, groups};
}
}
return best;
}
// Blocks k contain the two candidates 6k+1 and 6k+5. This tests a
// prefix consisting of groups*d whole blocks, where d is 2,3-smooth.
bool coprime_prefix_has_multiple(int64 first_block, const Step& step) {
const int64 c = 6 * step.d;
const int64 first_value = 6 * first_block + 1;
std::vector<int64> query;
query.reserve(static_cast<std::size_t>(2 * step.d + step.groups));
for (int64 a = 1; a <= c; ++a) {
if (a % 6 == 0 || a % 6 == 2) {
query.push_back(scaled(a, SCALE));
}
}
for (int64 j = 1; j <= step.groups; ++j) {
query.push_back(scaled(first_value + j * c, SCALE));
}
return collisions(std::move(query)) != 0;
}
int64 find_coprime_multiple() {
constexpr int64 LOWER = 200000000;
constexpr int64 UPPER = 1000000000;
int64 low = (LOWER - 1) / 6;
int64 high = (UPPER - 1) / 6;
const std::vector<int64> steps = smooth_steps();
while (low < high) {
const int64 block_count = high - low + 1;
const int64 half = block_count / 2;
const Step step = choose_step(half, steps);
const int64 taken = step.d * step.groups;
if (coprime_prefix_has_multiple(low, step)) {
high = low + taken - 1;
} else {
low += taken;
}
}
const int64 x1 = 6 * low + 1;
if (collisions({SCALE, scaled(x1 + 1, SCALE)}) != 0) return x1;
return 6 * low + 5;
}
int64 integer_power(int64 base, int exponent) {
int64 result = 1;
while (exponent-- > 0) result *= base;
return result;
}
int recover_answer(int64 multiple) {
std::vector<std::pair<int64, int>> factors;
int64 remaining = multiple;
for (int64 p = 2; p <= remaining / p; ++p) {
if (remaining % p != 0) continue;
int exponent = 0;
do {
remaining /= p;
++exponent;
} while (remaining % p == 0);
factors.push_back({p, exponent});
}
if (remaining > 1) factors.push_back({remaining, 1});
int64 answer = multiple;
for (const auto& [prime, exponent] : factors) {
int low = 0, high = exponent;
while (low < high) {
const int mid = (low + high + 1) / 2;
const int64 candidate = answer / integer_power(prime, mid);
if (collisions({1, candidate + 1}) != 0) {
low = mid;
} else {
high = mid - 1;
}
}
answer /= integer_power(prime, low);
}
return static_cast<int>(answer);
}
} // namespace
int hack() {
const int64 limit2 = LIMIT_N / POW2;
if (prefix_has_multiple(limit2, POW2)) {
return recover_answer(POW2 * find_effective_modulus(limit2, POW2));
}
const int64 limit3 = LIMIT_N / POW3;
if (prefix_has_multiple(limit3, POW3)) {
return recover_answer(POW3 * find_effective_modulus(limit3, POW3));
}
if (prefix_has_multiple(SMALL_M, SCALE)) {
return recover_answer(SCALE * find_effective_modulus(SMALL_M, SCALE));
}
return recover_answer(SCALE * find_coprime_multiple());
}随便找了一些数，都在八万左右，完全胜利。
算法四
突破人类的极限。
一次 collisions(x) 会统计所有满足 $i
直接寻找 $n$ 的倍数很困难。先把询问中的每个数都乘上同一个正整数 $S$。若两个未缩放的询问数之差为 $d$，那么
$$ n\mid Sd \iff \frac{n}{\gcd(n,S)}\mid d. $$
记 $D=n/\gcd(n,S)$。缩放后的询问实际面对的是有效模数 $D$。如果 $S$ 含有 $n$ 的一些小质因子，这些因子就会从 $D$ 中消失。算法四用固定的 $S$ 消去 $2,3,5$，先找到剩余部分的一个倍数，再由这个倍数还原 $n$。
先介绍一个判断 $D\le R$ 的通用询问。令 $C=\lceil\sqrt R\rceil$，询问下列所有数乘上 $S$ 后的结果：
$$ 1,2,\ldots,C,C+1,2C+1,3C+1,\ldots,R+1. $$
实现时，等差数列只加入不超过 $R$ 的项，最后单独加入 $R+1$。这些数的正差恰好覆盖 $[1,R]$。对任意 $d\in[1,R]$，在后半部分中取最小的、严格大于 $d$ 的数 $y$。后半部分相邻两项的距离不超过 $C$，所以 $1\le y-d\le C$；询问中同时含有 $y$ 和 $y-d$，两数之差就是 $d$。反过来，询问中的最大数为 $R+1$、最小数为 $1$，任意正差都不超过 $R$。因此询问有碰撞，当且仅当 $[1,R]$ 中含有 $D$ 的正倍数，也就是 $D\le R$。询问长度约为 $2\sqrt R$，而判定结果关于 $R$ 单调，所以也能用它二分 $D$。
算法四取
$$ S=2^{10}\cdot3^6\cdot5^4=466560000,qquad R=\left\lfloor\frac{10^9}{5^4}\right\rfloor=1600000. $$
先检查 $D\le R$。如果有碰撞，就在 $[1,R]$ 上二分，每次判断 $D\le\mathrm{mid}$，从而求出准确的 $D$。此时 $K=SD$ 一定是 $n$ 的倍数，可以直接进入最后的还原过程。
如果没有碰撞，则 $D>R$。将 $n$ 写成 $n=2^a3^b5^cm$，其中 $\gcd(m,30)=1$。若 $a\ge10$，就有 $D\le n/2^{10}R$ 矛盾，因此 $a\le9,b\le5,c\le3$。此时 $S$ 已包含 $n$ 的全部 $2,3,5$ 因子，所以 $D=m>1600000$，并且 $m$ 与 $30$ 互质。
现在要在 $[L,U]=[142857143,10^9]$ 中寻找一个与 $30$ 互质的 $m$ 的倍数。这个区间中一定存在目标。若 $m\ge L$，可直接取 $m$；否则，令 $q$ 是满足 $qm\ge L$ 且 $\gcd(q,30)=1$ 的最小正整数，令 $q'$ 是 $q$ 之前最大的、与 $30$ 互质的正整数。由于 $7q'$ 仍与 $30$ 互质，而 $q$ 是 $q'$ 后的第一个合法整数，所以 $q\le7q'$。又因为 $q'm
$$ qm\le7q'm\le7(L-1)=999999994
$q$ 和 $m$ 都与 $30$ 互质，因此 $qm$ 正是搜索区间中的一个合法目标。
把整数按长度为 $30$ 分块。第 $k$ 块只保留 $30k+r$，其中 $r\in\{1,7,11,13,17,19,23,29\}$，也就是每块的八个与 $30$ 互质的数。接下来构造一次询问，判断从当前第一个块 $B$ 开始的若干完整块中是否含有目标。
选一个只含质因子 $2,3,5$ 的正整数 $d$，令 $C=30d$。询问的第一部分为
$$ A=\{a\in[1,C]:\gcd(a-1,30)=1\}, $$
第二部分为 $P_j=30B+1+jC$，其中 $1\le j\le g$。固定 $j$ 后，因为 $P_j\equiv1\pmod {30}$，所以 $P_j-a$ 与 $30$ 互质，当且仅当 $a-1$ 与 $30$ 互质。当 $a$ 遍历 $A$ 时，差 $P_j-a$ 恰好遍历紧邻 $P_j$ 之前、长度为 $C$ 的区间中所有与 $30$ 互质的数，也就是 $d$ 个完整块的全部候选。所有 $j$ 合起来便恰好覆盖从第 $B$ 块开始的 $gd$ 个完整块。
第一部分有 $8d$ 个数，第二部分有 $g$ 个数，所以费用为 $8d+g$。还要证明两部分内部不会产生无关碰撞。第一部分任意两数之差小于 $C$；代码保证 $C\le40500
设当前共有 $T$ 个块，希望检查约一半的 $H=\lfloor T/2\rfloor$ 个块。代码枚举所有不超过 $1350$ 的 $2,3,5$-光滑数 $d$，令 $g=\lfloor H/d\rfloor$，并选择使 $8d+g$ 最小的一组参数。有碰撞就保留覆盖的前缀，没有碰撞就删除它。每轮都至少处理一个块，最终只剩一个模 $30$ 块。
最后一个块只有八个候选数，而且块宽 $30
已知 $n\mid K$ 后，先分解 $K$。对每个质因子 $p$，二分最大的 $t$，询问 $\{1,K/p^t+1\}$。询问有碰撞当且仅当 $n\mid K/p^t$，所以可以安全删除这 $t$ 个因子 $p$。处理过程中当前数始终是 $n$ 的倍数。全部质因子处理完后，若当前数仍大于 $n$，商中必然还有某个质因子 $p$，再除以 $p$ 后仍会是 $n$ 的倍数，这与 $p$ 已经无法继续删除矛盾。因此最后得到的数恰好是 $n$。
算法四的前置费用为 $2530$。按照代码实际使用的离散步长逐轮计算，分块搜索费用不超过 $73018$，最后定位和恢复 $n$ 共不超过 $50$，确定性费用上界为 $75598$。生成询问的本地时间与总费用同阶；试除过程中固定的小质因子会很快被除尽，剩余部分不超过 $10^9$，质因数分解需要 $O(\sqrt{10^9})$ 的本地时间。额外空间不超过一次询问数组的长度。所有询问数都小于 $10^{18}$，同一次询问中的数也互不相同。
代码
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>
int hack();
long long collisions(std::vector<long long> x);
namespace {
using i64 = long long;
constexpr i64 N_LIMIT = 1000000000LL;
constexpr i64 SCALE = (1LL << 10) * 729 * 625; // 2^10 * 3^6 * 5^4
constexpr i64 SMALL_LIMIT = N_LIMIT / 625;
constexpr i64 MAX_SPAN = 40500;
constexpr i64 WHEEL = 30;
constexpr int PHI = 8;
i64 ceil_sqrt(i64 x) {
i64 r = static_cast<i64>(std::sqrt(static_cast<long double>(x)));
while (r * r < x) ++r;
while (r > 1 && (r - 1) * (r - 1) >= x) --r;
return r;
}
// 询问中的差恰好覆盖 [1, limit]，从而判断有效模数是否不超过 limit。
bool check_prefix(i64 limit) {
const i64 width = ceil_sqrt(limit);
std::vector<i64> query;
query.reserve(static_cast<std::size_t>(width + limit / width + 2));
for (i64 x = 1; x <= width; ++x) query.push_back(SCALE * x);
for (i64 x = width + 1; x <= limit; x += width) {
query.push_back(SCALE * x);
}
query.push_back(SCALE * (limit + 1));
return collisions(std::move(query)) != 0;
}
// 调用前已经确定有效模数位于 [1, limit]。
i64 find_small_modulus(i64 limit) {
i64 low = 1, high = limit;
while (low < high) {
const i64 mid = (low + high) / 2;
if (check_prefix(mid)) high = mid;
else low = mid + 1;
}
return low;
}
std::vector<i64> build_smooth_steps() {
constexpr i64 MAX_STEP = MAX_SPAN / WHEEL;
std::vector<i64> steps;
for (i64 p2 = 1; p2 <= MAX_STEP; p2 *= 2) {
for (i64 p23 = p2; p23 <= MAX_STEP; p23 *= 3) {
for (i64 d = p23; d <= MAX_STEP; d *= 5) {
steps.push_back(d);
if (d > MAX_STEP / 5) break;
}
if (p23 > MAX_STEP / 3) break;
}
}
std::sort(steps.begin(), steps.end());
steps.erase(std::unique(steps.begin(), steps.end()), steps.end());
return steps;
}
struct Step {
i64 length;
i64 groups;
};
Step choose_step(i64 target, const std::vector<i64>& steps) {
Step best{0, 0};
i64 best_cost = std::numeric_limits<i64>::max();
for (i64 length : steps) {
if (length > target) break;
const i64 groups = target / length;
if (groups >= SMALL_LIMIT) continue;
const i64 cost = PHI * length + groups;
if (cost < best_cost) {
best_cost = cost;
best = {length, groups};
}
}
return best;
}
// 判断从 first_block 开始的 length * groups 个完整块中是否有目标。
bool check_blocks(i64 first_block, const Step& step) {
const i64 span = WHEEL * step.length;
const i64 first_value = WHEEL * first_block + 1;
std::vector<i64> query;
query.reserve(static_cast<std::size_t>(
PHI * step.length + step.groups));
for (i64 a = 1; a <= span; ++a) {
if (std::gcd(a - 1, WHEEL) == 1) query.push_back(SCALE * a);
}
for (i64 j = 1; j <= step.groups; ++j) {
query.push_back(SCALE * (first_value + j * span));
}
return collisions(std::move(query)) != 0;
}
i64 find_coprime_multiple() {
constexpr i64 LOWER = 142857143;
constexpr i64 UPPER = 1000000000;
constexpr int RESIDUES[] = {1, 7, 11, 13, 17, 19, 23, 29};
i64 low = (LOWER - 1) / WHEEL;
i64 high = (UPPER - 1) / WHEEL;
const std::vector<i64> steps = build_smooth_steps();
while (low < high) {
const i64 block_count = high - low + 1;
const Step step = choose_step(block_count / 2, steps);
const i64 covered = step.length * step.groups;
if (check_blocks(low, step)) high = low + covered - 1;
else low += covered;
}
int left = 0, right = 7;
while (left < right) {
const int mid = (left + right) / 2;
std::vector<i64> query{SCALE};
query.reserve(static_cast<std::size_t>(mid - left + 2));
for (int i = left; i <= mid; ++i) {
const i64 x = WHEEL * low + RESIDUES[i];
query.push_back(SCALE * (x + 1));
}
if (collisions(std::move(query)) != 0) right = mid;
else left = mid + 1;
}
return WHEEL * low + RESIDUES[left];
}
i64 integer_power(i64 base, int exponent) {
i64 result = 1;
while (exponent-- > 0) result *= base;
return result;
}
std::vector<std::pair<i64, int>> factorize(i64 value) {
std::vector<std::pair<i64, int>> factors;
for (i64 p = 2; p <= value / p; ++p) {
if (value % p != 0) continue;
int exponent = 0;
do {
value /= p;
++exponent;
} while (value % p == 0);
factors.push_back({p, exponent});
}
if (value > 1) factors.push_back({value, 1});
return factors;
}
// multiple 始终保持为 n 的倍数，依次删除每个质因子的多余指数。
int recover_n(i64 multiple) {
const auto factors = factorize(multiple);
for (const auto& [prime, exponent] : factors) {
int low = 0, high = exponent;
while (low < high) {
const int mid = (low + high + 1) / 2;
const i64 candidate =
multiple / integer_power(prime, mid);
if (collisions({1, candidate + 1}) != 0) low = mid;
else high = mid - 1;
}
multiple /= integer_power(prime, low);
}
return static_cast<int>(multiple);
}
} // namespace
int hack() {
if (check_prefix(SMALL_LIMIT)) {
return recover_n(SCALE * find_small_modulus(SMALL_LIMIT));
}
return recover_n(SCALE * find_coprime_multiple());
}算法五
算法四只消去了 $2,3,5$。继续让 $S$ 包含其他小质数，可以降低主搜索中的候选密度，但不一定降低总费用：质数种类越多，在 $10^{18}$ 的限制下能分配给每个质数的幂次越低，前置判定范围就越大；筛选模数 $M$ 越大，一块中与 $M$ 互质的剩余类数量 $\varphi(M)$ 也可能越多，搜索末尾仍要支付这部分固定费用。
若从头到尾只使用一个模数，原方案枚举可行参数后得到：
| 消去的质因子 | 主搜索费用 | 前置费用 | 收尾上界 | 总上界 |
|---|---|---|---|---|
| $\{2,3\}$ | $78868$ | $451$ | $42$ | $79361$ |
| $\{2,3,5\}$ | $73018$ | $2530$ | $50$ | $75598$ |
| $\{2,3,5,11\}$ | $69880$ | $5750$ | $126$ | $75756$ |
| 最优五质数组合 | $69613$ | $12172$ | $526$ | $82311$ |
$\{2,3,5,11\}$ 已把主搜索费用降到 $69880$，但模 $330$ 有 $80$ 个互质剩余类，收尾费用偏高。算法五在区间很大时使用模 $330$；区间缩小后切换到模 $30$，最后切换到模 $6$。新增候选只出现在很小的区间里，而每轮询问第一部分的规模会从 $80d$ 降到 $8d$，再降到 $2d$。
取 $S=2^7\cdot3^5\cdot5^3\cdot11^2=470448000$，并令 $R=\lfloor10^9/11^2\rfloor=8264462$。仍先使用算法四的前缀判定。若没有碰撞，则 $D>R$。写成 $n=2^a3^b5^c11^dm$，其中 $\gcd(m,330)=1$。如果 $a\ge7$、$b\ge5$、$c\ge3$ 或 $d\ge2$，有效模数分别不超过 $n/2^7,n/3^5,n/5^3,n/11^2$，都会不超过 $R$，产生矛盾。因此 $a\le6,b\le4,c\le2,d\le1$。此时 $S$ 已包含 $n$ 的全部 $2,3,5,11$ 因子，主分支中的有效模数就是 $m>8264462$，且 $\gcd(m,330)=1$。
若前缀判定有碰撞，则 $D\le8264462$。一直用前缀判定二分虽然正确，但每轮费用仍接近 $2\sqrt R$。代码先检查 $D\le4096$；若成立，就在 $[1,4096]$ 上用前缀判定二分。否则已知 $D>4096$，接下来使用区间判定。
要判断 $[l,r]$ 中是否含有 $D$ 的倍数，令 $C=\lceil\sqrt{r-l+1}\rceil$，询问 $1,2,\ldots,C,l+C,l+2C,\ldots,r+1$ 乘上 $S$ 后的结果。第一部分和第二部分的交叉差覆盖整个 $[l,r]$：$l+C$ 与 $[1,C]$ 作差覆盖第一段，后面的等差数列项依次覆盖后续各段，$r+1$ 补齐末尾。
已知 $D>C$ 时，第一部分内部不会碰撞。第二部分在模 $D$ 下以步长 $C$ 前进，只经过同一个模 $g=\gcd(C,D)$ 的剩余类。如果它在命中第一部分前已经重复，就说明它走完了长度为 $D/g$ 的一整圈。因为 $g\le C$，$[1,C]$ 中必有一个数与第二部分同余模 $g$；走完整圈时，第二部分必然也会与这个数同余模 $D$。因此第二部分的内部碰撞只可能与一次真实的交叉碰撞同时出现，不会制造假阳性。
区间二分第一次只询问当前范围的左半边，此时 $C\le2033
主分支在 $[142857143,10^9]$ 中寻找一个与 $330$ 互质的 $m$ 的倍数。目标存在性的证明与算法四相同：$7$ 与 $330$ 互质，所以相邻两个与 $330$ 互质的正整数之比不超过 $7$，上述区间必然包含目标。
把分块询问推广到 $M\in\{330,30,6\}$。第 $k$ 个模 $M$ 块保留所有 $Mk+r$，其中 $1\le r\le M$ 且 $\gcd(r,M)=1$；三个模数每块分别有 $80,8,2$ 个候选。选一个只含质因子 $2,3,5,11$ 的正整数 $d$，令 $C=Md$。若当前第一个块为 $B$，询问
$$ A=\{a\in[1,C]:\gcd(a-1,M)=1\} $$
以及 $P_j=MB+1+jC\ (1\le j\le g)$。因为 $P_j\equiv1\pmod M$，所以 $P_j-a$ 与 $M$ 互质，当且仅当 $a-1$ 与 $M$ 互质。固定 $j$ 时，交叉差恰好覆盖 $d$ 个完整块的全部候选；所有 $j$ 合起来覆盖从第 $B$ 块开始的 $gd$ 个块，费用为 $\varphi(M)d+g$。
代码只枚举 $d\le2048$，所以第一部分任意两数之差小于 $Md\le675840
每轮枚举所有不超过 $2048$ 的 $2,3,5,11$-光滑数 $d$，令 $g=\lfloor H/d\rfloor$，其中 $H$ 是希望覆盖的约一半块数，再选择使 $\varphi(M)d+g$ 最小的方案。有碰撞就保留前缀，否则删除前缀。模 $330$ 区间缩小到不超过 $80$ 个块后，每个旧块展开为 $11$ 个模 $30$ 块：$\mathrm{low}'=11\mathrm{low}$，$\mathrm{high}'=11(\mathrm{high}+1)-1$。目标与 $330$ 互质，自然也与 $30$ 互质，所以不会丢失。模 $30$ 区间缩小到不超过 $4$ 个块后，再把每块展开成 $5$ 个模 $6$ 块。最后一个模 $6$ 块只有 $6k+1$ 和 $6k+5$ 两个候选，用一次二元询问即可确定目标。
找到 $x$ 后，$K=Sx$ 是 $n$ 的倍数。主分支已经知道 $v_2(n)\le6,v_3(n)\le4,v_5(n)\le2,v_{11}(n)\le1$，所以 $K$ 中超过这些上界的对应质因子可以直接删除；随后再按算法四的方法二分其余可删除指数。提前命中分支没有得到指数上界，不能执行直接删除。
按代码的离散步长逐轮计算，前置费用为 $5750$，三层搜索和最后定位为 $69653$，恢复 $n$ 不超过 $38$，确定性总费用不超过 $75441$。生成询问需要 $O(Q)$ 的本地时间，其中 $Q\le75441$；试除需要 $O(\sqrt{10^9})$，额外空间不超过一次询问数组。最大询问数为 $470448000\times1000000321=470448151013808000<10^{18}$。代码只有常量全局变量，不会在多次 hack() 调用之间残留状态。
代码
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>
int hack();
long long collisions(std::vector<long long> x);
namespace {
using i64 = long long;
constexpr i64 N_LIMIT = 1000000000LL;
constexpr i64 SCALE = 128 * 243 * 125 * 121LL; // 2^7 * 3^5 * 5^3 * 11^2
constexpr i64 SMALL_LIMIT = N_LIMIT / 121;
constexpr i64 DIRECT_LIMIT = 4096;
constexpr i64 MAX_STEP = 2048;
constexpr i64 MODS[] = {330, 30, 6};
constexpr i64 PHIS[] = {80, 8, 2};
constexpr i64 STOP_BLOCKS[] = {80, 4, 1};
constexpr i64 RATIOS[] = {11, 5};
i64 ceil_sqrt(i64 x) {
i64 r = static_cast<i64>(std::sqrt(static_cast<long double>(x)));
while (r * r < x) ++r;
while (r > 1 && (r - 1) * (r - 1) >= x) --r;
return r;
}
// 询问中的差恰好覆盖 [1, limit]，从而判断有效模数是否不超过 limit。
bool check_prefix(i64 limit) {
const i64 width = ceil_sqrt(limit);
std::vector<i64> query;
query.reserve(static_cast<std::size_t>(width + limit / width + 2));
for (i64 x = 1; x <= width; ++x) query.push_back(SCALE * x);
for (i64 x = width + 1; x <= limit; x += width) {
query.push_back(SCALE * x);
}
query.push_back(SCALE * (limit + 1));
return collisions(std::move(query)) != 0;
}
// 已知有效模数大于 width 时，判断 [left, right] 中是否有它的倍数。
bool check_interval(i64 left, i64 right) {
const i64 width = ceil_sqrt(right - left + 1);
std::vector<i64> query;
query.reserve(static_cast<std::size_t>(
width + (right - left + 1) / width + 2));
for (i64 x = 1; x <= width; ++x) query.push_back(SCALE * x);
for (i64 x = left + width; x <= right; x += width) {
query.push_back(SCALE * x);
}
query.push_back(SCALE * (right + 1));
return collisions(std::move(query)) != 0;
}
i64 find_small_modulus(i64 limit) {
i64 low = 1, high = limit;
while (low < high) {
const i64 mid = (low + high) / 2;
if (check_prefix(mid)) high = mid;
else low = mid + 1;
}
return low;
}
// 调用前已经确定有效模数不超过 SMALL_LIMIT。
i64 find_effective_modulus() {
if (check_prefix(DIRECT_LIMIT)) {
return find_small_modulus(DIRECT_LIMIT);
}
i64 low = DIRECT_LIMIT + 1, high = SMALL_LIMIT;
while (low < high) {
const i64 mid = (low + high) / 2;
if (check_interval(low, mid)) high = mid;
else low = mid + 1;
}
return low;
}
void generate_smooth_steps(int index, i64 value,
std::vector<i64>& steps) {
constexpr int PRIMES[] = {2, 3, 5, 11};
if (index == 4) {
steps.push_back(value);
return;
}
while (true) {
generate_smooth_steps(index + 1, value, steps);
if (value > MAX_STEP / PRIMES[index]) break;
value *= PRIMES[index];
}
}
std::vector<i64> build_smooth_steps() {
std::vector<i64> steps;
generate_smooth_steps(0, 1, steps);
std::sort(steps.begin(), steps.end());
steps.erase(std::unique(steps.begin(), steps.end()), steps.end());
return steps;
}
struct Step {
i64 length;
i64 groups;
};
Step choose_step(i64 target, i64 phi,
const std::vector<i64>& steps) {
Step best{0, 0};
i64 best_cost = std::numeric_limits<i64>::max();
for (i64 length : steps) {
if (length > target) break;
const i64 groups = target / length;
const i64 cost = phi * length + groups;
if (cost < best_cost) {
best_cost = cost;
best = {length, groups};
}
}
return best;
}
// 判断从 first_block 开始的 length * groups 个完整块中是否有目标。
bool check_blocks(i64 first_block, const Step& step,
i64 mod, i64 phi) {
const i64 span = mod * step.length;
const i64 first_value = mod * first_block + 1;
std::vector<i64> query;
query.reserve(static_cast<std::size_t>(
phi * step.length + step.groups));
for (i64 a = 1; a <= span; ++a) {
if (std::gcd(a - 1, mod) == 1) query.push_back(SCALE * a);
}
for (i64 j = 1; j <= step.groups; ++j) {
query.push_back(SCALE * (first_value + j * span));
}
return collisions(std::move(query)) != 0;
}
void narrow_blocks(i64& low, i64& high, int level,
const std::vector<i64>& steps) {
const i64 mod = MODS[level];
const i64 phi = PHIS[level];
while (high - low + 1 > STOP_BLOCKS[level]) {
const i64 block_count = high - low + 1;
const Step step = choose_step(block_count / 2, phi, steps);
const i64 covered = step.length * step.groups;
if (check_blocks(low, step, mod, phi)) {
high = low + covered - 1;
} else {
low += covered;
}
}
}
i64 find_coprime_multiple() {
constexpr i64 LOWER = 142857143;
constexpr i64 UPPER = 1000000000;
const std::vector<i64> steps = build_smooth_steps();
i64 low = (LOWER - 1) / MODS[0];
i64 high = (UPPER - 1) / MODS[0];
narrow_blocks(low, high, 0, steps);
low *= RATIOS[0];
high = (high + 1) * RATIOS[0] - 1;
narrow_blocks(low, high, 1, steps);
low *= RATIOS[1];
high = (high + 1) * RATIOS[1] - 1;
narrow_blocks(low, high, 2, steps);
const i64 first = MODS[2] * low + 1;
if (collisions({SCALE, SCALE * (first + 1)}) != 0) return first;
return MODS[2] * low + 5;
}
i64 integer_power(i64 base, int exponent) {
i64 result = 1;
while (exponent-- > 0) result *= base;
return result;
}
void strip_known_excess(i64& multiple, i64 prime,
int maximum_exponent) {
int exponent = 0;
for (i64 x = multiple; x % prime == 0; x /= prime) ++exponent;
if (exponent > maximum_exponent) {
multiple /= integer_power(prime, exponent - maximum_exponent);
}
}
std::vector<std::pair<i64, int>> factorize(i64 value) {
std::vector<std::pair<i64, int>> factors;
for (i64 p = 2; p <= value / p; ++p) {
if (value % p != 0) continue;
int exponent = 0;
do {
value /= p;
++exponent;
} while (value % p == 0);
factors.push_back({p, exponent});
}
if (value > 1) factors.push_back({value, 1});
return factors;
}
// multiple 始终保持为 n 的倍数，依次删除每个质因子的多余指数。
int recover_n(i64 multiple, bool exponents_are_bounded) {
if (exponents_are_bounded) {
strip_known_excess(multiple, 2, 6);
strip_known_excess(multiple, 3, 4);
strip_known_excess(multiple, 5, 2);
strip_known_excess(multiple, 11, 1);
}
const auto factors = factorize(multiple);
for (const auto& [prime, exponent] : factors) {
int low = 0, high = exponent;
while (low < high) {
const int mid = (low + high + 1) / 2;
const i64 candidate =
multiple / integer_power(prime, mid);
if (collisions({1, candidate + 1}) != 0) low = mid;
else high = mid - 1;
}
multiple /= integer_power(prime, low);
}
return static_cast<int>(multiple);
}
} // namespace
int hack() {
if (check_prefix(SMALL_LIMIT)) {
return recover_n(SCALE * find_effective_modulus(), false);
}
return recover_n(SCALE * find_coprime_multiple(), true);
}算法六
我们可以做到 73744，此处暂且不发布。
代码
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <limits>
#include <numeric>
#include <utility>
#include <vector>
int hack();
long long collisions(std::vector<long long> x);
namespace {
using int64 = long long;
constexpr int64 LIMIT_N = 1000000000LL;
constexpr int64 POW2 = 128; // 2^7
constexpr int64 POW3 = 243; // 3^5
constexpr int64 POW5 = 125; // 5^3
constexpr int64 POW11 = 121; // 11^2
constexpr int64 SCALE = POW2 * POW3 * POW5 * POW11;
constexpr int64 EARLY_LIMIT = LIMIT_N / POW11;
constexpr int64 DIRECT_LIMIT = 4096;
constexpr int64 MAX_STEP = 2048;
static_assert(330 * MAX_STEP < EARLY_LIMIT + 1);
constexpr int64 MODS[] = {330, 30, 6};
constexpr int64 PHIS[] = {80, 8, 2};
constexpr int64 STOPS[] = {81, 4, 1};
constexpr int64 RATIOS[] = {11, 5};
int64 scaled(int64 x, int64 scale) {
return x * scale;
}
bool prefix_has_multiple(int64 r, int64 scale) {
// It is enough to cover differences in [ceil(r/2), r]: every positive
// d <= r has a multiple in that interval. A short arithmetic difference
// basis covers this upper half with about sqrt(2*r) queried numbers.
const int64 lower = (r + 1) / 2;
int64 width = static_cast<int64>(
std::sqrt(static_cast<long double>(r) / 2.0L));
while ((width + 1) * (width + 1) <= (r + 1) / 2) ++width;
while (width * width > (r + 1) / 2) --width;
if (width < 1) width = 1;
std::vector<int64> query;
const int64 first = lower + width;
query.reserve(static_cast<std::size_t>(width + r / (2 * width) + 3));
for (int64 i = 1; i <= width; ++i) {
query.push_back(scaled(i, scale));
}
for (int64 x = first; x <= r + 1; x += width) {
query.push_back(scaled(x, scale));
}
if (query.back() != scaled(r + 1, scale)) {
query.push_back(scaled(r + 1, scale));
}
return collisions(std::move(query)) != 0;
}
bool interval_has_multiple(int64 left, int64 right, int64 scale) {
const int64 length = right - left + 1;
int64 c = static_cast<int64>(
std::sqrt(static_cast<long double>(length)));
while (c * c < length) ++c;
std::vector<int64> query;
query.reserve(static_cast<std::size_t>(c + length / c + 2));
for (int64 i = 1; i <= c; ++i) query.push_back(scaled(i, scale));
for (int64 x = left + c; x <= right; x += c) {
query.push_back(scaled(x, scale));
}
query.push_back(scaled(right + 1, scale));
return collisions(std::move(query)) != 0;
}
int64 find_small_effective_modulus(int64 limit, int64 scale) {
int64 low = 1, high = limit;
while (low < high) {
const int64 mid = (low + high) / 2;
if (prefix_has_multiple(mid, scale)) high = mid;
else low = mid + 1;
}
return low;
}
int64 find_effective_modulus(int64 limit, int64 scale) {
if (prefix_has_multiple(DIRECT_LIMIT, scale)) {
return find_small_effective_modulus(DIRECT_LIMIT, scale);
}
int64 low = DIRECT_LIMIT + 1, high = limit;
while (low < high) {
const int64 mid = (low + high) / 2;
if (interval_has_multiple(low, mid, scale)) high = mid;
else low = mid + 1;
}
return low;
}
std::vector<int64> step_candidates() {
std::vector<int64> result;
// In the main branch m > EARLY_LIMIT. Since every queried arithmetic
// progression has fewer than m steps, an arbitrary d is safe as long as
// M*d < m; no smoothness restriction is needed here.
for (int64 d = 1; d <= MAX_STEP; ++d) result.push_back(d);
std::sort(result.begin(), result.end());
result.erase(std::unique(result.begin(), result.end()), result.end());
return result;
}
struct Step {
int64 d;
int64 groups;
};
Step choose_step(int64 half, int64 phi,
const std::vector<int64>& steps) {
Step best{0, 0};
int64 best_cost = std::numeric_limits<int64>::max();
for (int64 d : steps) {
if (d > half) break;
const int64 groups = half / d;
const int64 cost = phi * d + groups;
if (cost < best_cost) {
best_cost = cost;
best = {d, groups};
}
}
return best;
}
long long wheel_prefix_collisions(int64 first_block, const Step& step,
int64 modulus, int64 phi) {
const int64 c = modulus * step.d;
const int64 first_value = modulus * first_block + 1;
std::vector<int64> query;
query.reserve(static_cast<std::size_t>(phi * step.d + step.groups));
for (int64 a = 1; a <= c; ++a) {
if (std::gcd(a - 1, modulus) == 1) {
query.push_back(scaled(a, SCALE));
}
}
for (int64 j = 1; j <= step.groups; ++j) {
query.push_back(scaled(first_value + j * c, SCALE));
}
return collisions(std::move(query));
}
void narrow_blocks_plain(int64& low, int64& high, int level,
int64 stop_at, const std::vector<int64>& steps) {
while (high - low + 1 > stop_at) {
const int64 block_count = high - low + 1;
const Step step = choose_step(block_count / 2, PHIS[level], steps);
const int64 taken = step.d * step.groups;
if (wheel_prefix_collisions(low, step, MODS[level], PHIS[level])) {
high = low + taken - 1;
} else {
low += taken;
}
}
}
int64 estimate_remaining_cost(int level, int64 block_count,
const std::vector<int64>& steps) {
int64 result = 0;
for (int current = level; current < 3; ++current) {
while (block_count > STOPS[current]) {
const Step step = choose_step(block_count / 2,
PHIS[current], steps);
result += PHIS[current] * step.d + step.groups;
block_count -= step.d * step.groups;
}
if (current < 2) block_count *= RATIOS[current];
}
return result + 2;
}
int64 locate_from_big_blocks(int64 low, int64 high,
const std::vector<int64>& steps) {
narrow_blocks_plain(low, high, 0, STOPS[0], steps);
low *= RATIOS[0];
high = (high + 1) * RATIOS[0] - 1;
narrow_blocks_plain(low, high, 1, STOPS[1], steps);
low *= RATIOS[1];
high = (high + 1) * RATIOS[1] - 1;
narrow_blocks_plain(low, high, 2, STOPS[2], steps);
const int64 x = MODS[2] * low + 1;
if (collisions({SCALE, scaled(x + 1, SCALE)})) return x;
return MODS[2] * low + 5;
}
int64 ceil_div(int64 numerator, int64 denominator) {
return (numerator + denominator - 1) / denominator;
}
int64 find_coprime_multiple() {
constexpr int64 LOWER = 142857143;
constexpr int64 UPPER = 1000000000;
constexpr int64 MAX_UNIT_GAP_330 = 10;
const std::vector<int64> steps = step_candidates();
int64 low = (LOWER - 1) / MODS[0];
int64 high = (UPPER - 1) / MODS[0];
int64 modulus_lower_bound = EARLY_LIMIT + 1;
while (high - low + 1 > STOPS[0]) {
const int64 block_count = high - low + 1;
const int64 target = block_count / 2;
const Step step = choose_step(target, PHIS[0], steps);
const int64 taken = step.d * step.groups;
const int64 covered_length = MODS[0] * taken;
const long long hit = wheel_prefix_collisions(
low, step, MODS[0], PHIS[0]);
if (hit == 0) {
modulus_lower_bound = std::max(
modulus_lower_bound,
ceil_div(covered_length + 1, MAX_UNIT_GAP_330));
} else if (hit == 1) {
modulus_lower_bound = std::max(
modulus_lower_bound,
ceil_div(covered_length + 1,
2 * MAX_UNIT_GAP_330));
}
if (hit) high = low + taken - 1;
else low += taken;
if (hit >= 2) {
const int64 modulus_upper_bound = std::min<int64>(
UPPER, (covered_length - 1) / (hit - 1));
if (modulus_lower_bound <= modulus_upper_bound) {
const int64 direct_low =
(modulus_lower_bound - 1) / MODS[0];
const int64 direct_high =
(modulus_upper_bound - 1) / MODS[0];
const int64 direct_cost = estimate_remaining_cost(
0, direct_high - direct_low + 1, steps);
const int64 normal_cost = estimate_remaining_cost(
0, high - low + 1, steps);
if (direct_cost < normal_cost) {
return locate_from_big_blocks(
direct_low, direct_high, steps);
}
}
}
}
low *= RATIOS[0];
high = (high + 1) * RATIOS[0] - 1;
narrow_blocks_plain(low, high, 1, STOPS[1], steps);
low *= RATIOS[1];
high = (high + 1) * RATIOS[1] - 1;
narrow_blocks_plain(low, high, 2, STOPS[2], steps);
const int64 x = MODS[2] * low + 1;
if (collisions({SCALE, scaled(x + 1, SCALE)})) return x;
return MODS[2] * low + 5;
}
int64 integer_power(int64 base, int exponent) {
int64 result = 1;
while (exponent-- > 0) result *= base;
return result;
}
void strip_known_excess(int64& multiple, int64 prime,
int maximum_answer_exponent) {
int exponent = 0;
for (int64 x = multiple; x % prime == 0; x /= prime) ++exponent;
if (exponent > maximum_answer_exponent) {
multiple /= integer_power(prime,
exponent - maximum_answer_exponent);
}
}
int recover_answer(int64 multiple, bool exponents_are_bounded) {
if (exponents_are_bounded) {
strip_known_excess(multiple, 2, 6);
strip_known_excess(multiple, 3, 4);
strip_known_excess(multiple, 5, 2);
strip_known_excess(multiple, 11, 1);
}
std::vector<std::pair<int64, int>> factors;
int64 remaining = multiple;
for (int64 p = 2; p <= remaining / p; ++p) {
if (remaining % p != 0) continue;
int exponent = 0;
do {
remaining /= p;
++exponent;
} while (remaining % p == 0);
factors.push_back({p, exponent});
}
if (remaining > 1) factors.push_back({remaining, 1});
int64 answer = multiple;
for (const auto& [prime, exponent] : factors) {
int low = 0, high = exponent;
while (low < high) {
const int mid = (low + high + 1) / 2;
const int64 candidate = answer / integer_power(prime, mid);
if (collisions({1, candidate + 1})) low = mid;
else high = mid - 1;
}
answer /= integer_power(prime, low);
}
return static_cast<int>(answer);
}
} // namespace
int hack() {
if (prefix_has_multiple(EARLY_LIMIT, SCALE)) {
return recover_answer(
SCALE * find_effective_modulus(EARLY_LIMIT, SCALE), false);
}
return recover_answer(SCALE * find_coprime_multiple(), true);
}