自动搬运

查看原文

来自洛谷，原作者为

	Milmon HN 高一最菜 OIer | 史上最菜的菜鸡 qaq | 快乐学习，认真刷题，努力进步！

搬运于2025-08-24 22:59:01，当前版本为作者最后更新于2024-05-20 14:37:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里讲一下赛时 20 分钟想到的垃圾做法。

对于 Alice，我们充分发扬人类智慧，考虑对任意 $2 \leq v \leq n$，都让 $X \bmod (v-1) + 1$ 向 $v$ 连边。

对于 Bob 只需把所有边的信息都用数论知识合并起来即可得出 $x$ 的值。

事实上，本题不需要 excrt，因为 $n$ 只有 $5000$。暴力枚举（假设已知答案模 $p$ 余 $q$，就每次把 $q$ 加上 $p$ 直到满足下一个同余条件）时间复杂度 $O(n^2)$，可以通过。并且取 $n=75$ 时可以通过赛时评测，峰值运行时间 $0$ 毫秒。

事实上，在交互库足够强的情况下，$n=75$ 无法保证一定得出正确答案，具体说明见文章结尾处。（事实上，也可以随机一个置换或者对 $X$ 随机异或一个数使得这个做法不容易被卡，但是我们追求完全确定性做法。）

#include<bits/stdc++.h>
#include"Alice.h"
using namespace std;
const int N=5000;

vector<pair<int,int>> Alice(){
    long long x=setN(N);
    vector<pair<int,int>> edges;
    for(int i=2;i<=N;i++)
        edges.emplace_back(x%(i-1)+1,i);
    return edges;
}

#include<bits/stdc++.h>
#include"Bob.h"
using namespace std;

long long Bob(vector<pair<int,int>> edges){
    __int128 answer=0,nowmod=1;
    for(pair<int,int> edge :edges){
        int r=edge.first-1,mod=edge.second-1;
        while(answer%mod!=r)answer+=nowmod;
        nowmod*=mod/__gcd(nowmod,(__int128)mod);
        if(nowmod>1e18)return answer;
    }
    return answer;
}

考虑优化，容易发现在最初的做法中，一些素数只要删除一次或者两次就无法对答案造成贡献，这样会产生大量的信息浪费，所以考虑构造 $a_i < i$，然后对于任意 $2 \leq v \leq n$，令 $X \bmod (a_v-1) + 1$ 向 $v$ 连边。（一开始想到了这么优化，结果因为脑子问题一直以为这么改是变劣的，直到 lhx 大神指点这样居然变优了。）

如果令 $a$ 中每个数为素数的幂，那么可以用暴力搜索和动态规划找出一个较优秀的解。在数列 $a$ 的细节继续优化，目前可以构造出数列 $a$ 使得只需要 $n = 99$ 个结点保证确定性。（之前的 $n=95$ 是错的）

1 2 3 4 5 5 7 7 9 9 11 11 11 13 13 13 16 17 17 17 19 19 19 23 23 23 25 25 27 29 29 29 29 31 31 31 31 32 37 37 37 37 41 41 41 41 43 43 43 43 47 47 47 47 49 49 53 53 53 53 59 59 59 59 61 61 61 61 64 67 67 67 67 71 71 71 71 71 73 73 73 73 79 79 79 79 83 83 83 83 83 89 89 89 89 79 97 97

直觉上 $n$ 可以再小，不知道能不能通过数学证明得出理论最小的 $n$，可是我太菜了。

附：最简易的数论做法需要 $n=615$ 可以保证通过：

• $n=614$ 时，取 $X=897,612,484,786,617,601=2^8 \times 3^4 \times 5^2 \times 7^2 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 \times 31 \times 37 + 1$，只有 $308$ 条边不可以保证得出正确答案。
• $n=615$ 时可以证明一定可以得出正确答案。