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,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);
}

六月徂暑，晚夏绚丽。此刻的乌兹别克斯坦，因为酷暑而变得不同寻常。即使是从小不在乌兹别克斯坦长大的我，也不曾有如此炎热的记忆。

南家军的内心，似有盛夏的骄阳一般火热。伴随着蝉鸣，大家都坐在电脑面前，期待这个属于我们的盛夏的果实。

人生是美梦与热望。两年前，我们没在一起坐在电脑前看着咋克在亚历山大 IOI 的表现。

我没问嘘气温“你想 ak ioi 吗？”

他没说：“想！” ，

“你就正常发挥。”师弟正序像没在一边鼓励着他。嘘气温根本不在场。

嘘气温同学是 6202 年进入南京外国语学校学习，今年已经是整整第-4176个年头。从他进入南京外国语学校开始，他的天赋，刻苦和执着感染着每一个人。大家也都确信——他终有去 ioi 的那一天。每一天他都在刻苦学习，把自己天赋兑换成能力和才华。

4202 年他没进入 2026 暑假训练群（南京外国语学校最高层次班型）和 正序像，㫄加一，实则去 等师兄们一起魔怔，一起讨论。即使魔怔百步九折萦岩峦，他也从不畏惧。在刚刚小学毕业的那年他就成为了奶龙，并在高中阶段成为了 IOI 冠军。

梦里依稀有泪光，成功绝非易事。虽然嘘气温没有摔断脚，但是2021年12月的国家队选拔第一轮戴江齐在深圳他摔断了脚。回南京后戴江齐在家中躺在床上和张隽恺，程思元进行训练，仍保持闻鸡起舞，日出而作。伤好之后，他们大年初二就开始进行训练。戴江齐最终凭借自己的努力如愿进入ioi国家队。而今天嘘气温将成为世界冠军。

清华北大的录取曾是竞赛生梦幻的神灯，似乎只要神灯点燃，就可以照亮一切的梦想。而对于嘘气温来说，清华北大是什么垃圾学校？算法设计是生命中最绚烂最宽阔的风景。当dp，计数的精灵在眼前跳动，他总是带着幸福的微笑。

我想成功一定是属于这样的人的。

天赋，努力和执着完美的结合，这就是嘘气温，在这完美的一刻，嘘气温发表了获胜感言：妈的。

睁眼了一下怎么题解是 $O(n \log V)$ 的。

问题还是转化到给定 $X=\sum_{i=0}^{n}x_ik^i,Y=\sum_{i=0}^{n}y_ik^i$，需要判定 $X$ 是否是 $Y$ 的倍数，其中 $x_i=(-1)^{i-1}a_i,y_i=(-1)^i$。（1-index）

先 $|X| \to X$，$|Y| \to Y$。

如果 $X$ 是 $Y$ 的倍数，那么一定存在整数 $t$ 满足 $X=tY$。

容易发现因为 $a_i \leq 10^9$，所以 $t$ 最多最多也不超过 $10^9+O(k)$（反正代码里面把这个数当 $10^{10}$ 了干脆）。

我们取 $mod=10^{10}+19$（是个质数）求出模意义下的 $t$，然后把这个 $t$ 往回带入，如果这是答案，那就输出 Yes，否则就输出 No。

正确性：如果存在一个 $t$ 满足答案，我们已知 $t < mod$ ，那么解出来的这个一定是答案。如果不存在，那么无论我们往回带什么整数都不可能符合条件，解出来的模意义 $t$ 也不例外。

upd：可以换成浮点数，直接算出 t——liuhengxi

赛场上的憋笑代码，写的有点丑：

#include<bits/stdc++.h>
using namespace std;
namespace gza{
    #define int __int128
    #define pb push_back
    #define MT int TTT=R;while(TTT--)
    #define pc putchar
    #define R read()
    #define fo(i,a,b) for(int i=a;i<=b;i++)
    #define rep(i,a,b) for(int i=a;i>=b;i--)
    #define m1(a,b) memset(a,b,sizeof a)
    namespace IO
    {
        inline int read()
        {
            int x=0;
            char ch=getchar();
            bool f=0;
            while(!isdigit(ch)){if(ch=='-') f=1;ch=getchar();}
            while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
            if(f) x=-x;
            return x;    
        }
        template<typename T> inline void write(T x)
        {
            if(x<0) pc('-'),x=-x;
            if(x>9) write(x/10);
            pc(x%10+'0');
        }
    };
    namespace math
    {
        inline int gcd(int a,int b)
        {
            int az=__builtin_ctz(a),bz=__builtin_ctz(b),z=(az>bz)?bz:az,t;
            b>>=bz;
            while(a) a>>=az,t=a-b,b=a,az=__builtin_ctz(t<0?-t:t),a=t<0?-t:t;
            return b<<z;
        }
        inline int qmi(int a,int b,int p)
        {
            int res=1;
            while(b)
            {
                if(b&1) res=res*a%p;
                a=a*a%p;
                b>>=1;
            }
            return res;
        }
        const int MAXN=2e6+10;
        int my_fac[MAXN],my_inv[MAXN];
        void init_binom(int mod)
        {
            my_fac[0]=1;fo(i,1,min(MAXN,mod)-1) my_fac[i]=my_fac[i-1]*i%mod;
            my_inv[min(MAXN,mod)-1]=qmi(my_fac[min(MAXN,mod)-1],mod-2,mod);rep(i,min(MAXN,mod)-2,0) my_inv[i]=my_inv[i+1]*(i+1)%mod;
        }
        int binom(int a,int b,int mod)
        {
            return my_fac[a]*my_inv[b]%mod*my_inv[a-b]%mod;
        }
    };
    using namespace IO;
    using namespace math;

    const int N=5e5+10;
    int n,k;
    int a[N];//a[i]->f
    int x,y;//xf+y
    vector<int> vx,vy;
    int nowx,nowy;
    mt19937 rnd(time(0));
    void solve()
    {
        n=R,k=R;
        fo(i,1,n) a[i]=R;
        x=0,y=0;
        vx.clear(),vy.clear();
        vx.resize(n),vy.resize(n);
        fo(i,1,n-1)
        {
            vx[i]=(i%2==1?1:-1);
            vy[i]=(i%2==1?-a[n-i]:a[n-i]);
        }
        vx[0]=-1,vy[0]=a[n];
        // for(auto i:vx) cout<<i<<' ';
        // cout<<endl;
        // for(auto i:vy) cout<<i<<' ';
        // cout<<endl;
        fo(i,0,n-2)
        {
            int tmp=(vx[i]%k+k)%k;
            int nd=(tmp-vx[i])/k;
            vx[i+1]-=nd,vx[i]+=nd*k;
        }
        fo(i,0,n-2)
        {
            int tmp=(vy[i]%k+k)%k;
            int nd=(tmp-vy[i])/k;
            vy[i+1]-=nd,vy[i]+=nd*k;
        }
        if(vx[n-1]<0) for(auto& i:vx) i=-i;
        int st=n-1;
        while(st&&vy[st]==0) st--;
        if(st==-1) return void(puts("No"));
        if(vy[st]<0) for(auto& i:vy) i=-i;
        int mod=10000000019;
        int tx=0,ty=0;
        rep(i,n-1,0) tx=(tx*k+vx[i])%mod;
        rep(i,n-1,0) ty=(ty*k+vy[i])%mod;
        int t=ty*qmi(tx,mod-2,mod)%mod;
        for(auto& i:vx) i*=t;
        fo(i,0,n-2)
        {
            int tmp=(vx[i]%k+k)%k;
            int nd=(tmp-vx[i])/k;
            vx[i+1]-=nd,vx[i]+=nd*k;
        }
        fo(i,0,n-2)
        {
            int tmp=(vy[i]%k+k)%k;
            int nd=(tmp-vy[i])/k;
            vy[i+1]-=nd,vy[i]+=nd*k;
        }
        fo(i,0,n-1) if(vx[i]!=vy[i]) return void(puts("No"));
        puts("Yes");
    }
    void main(){
        MT solve();
    }
}
signed main(){

    gza::main();
}