考场写的乱搞，现在想到一些让正确率更高的办法，我猜可以过，先写一下大体思路。
首先我们有 m 个方程 (a_i imes x + b_i = c_i (mod mod))，显然这个模意义方程是可以加减的，我们尝试构造一个方程：
(x + sum b_i = sum c_i)，这样如果 (b_i) 个数不多，就可以得到 x 的大体区间范围。
这时候我们再构造一组方程 (kx + sum b_i = sum c_i)，如果 k 不大，由刚刚求出的 x 范围，可以发现 kx 范围也不会很大，很大概率结果除 mod 相同，所以如果相同，我们可以得到一个新的方程 (kx = sum c_i - sum b_i - p imes mod)，列出不等式 (sum c_i - sum err - p imes mod le k imes x le sum c_i + sum err - p imes mod)，可以得到一个更加紧的范围，也可以继续更新其他的 k。
下面的问题是如何用比较少的方程构造出一个 (kx + sum b_i = sum c_i)，其中 k 不能太大。
我们考虑将所有方程按 (a_i) 排个序，然后拿 (a_i) 相邻的几个方程相减，可以得到 (a_i) 更加小的一些方程，如此迭代几次，效果应该不错，应该迭代层数也不会太大，好像迭代一层，(max_{a_i}) 就会期望变成 (frac{max_{a_i} log m}{m})，而且你可以保留更多的方程，(a_i) 缩减会更快。
大概按照上面这么写就有不少分了，应该可以加入一些随机化技巧，大胆猜测是可以过掉这题的。
upt: 过了
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using std::cerr;
typedef long long ll;
typedef long double ld;
std::mt19937_64 rd(114514);
const int maxn = 100100;
ll mod, err;
inline ll mul(ll x, ll y) {
ll res = x * y - ll((ld) x * y / mod + 0.5) * mod;
res += res >> 63 & mod;
return res;
}
inline ll add(ll x, ll y) { return x += y - mod, x + (x >> 63 & mod); }
inline ll sub(ll x, ll y) { return x -= y, x + (x >> 63 & mod); }
int T, m;
struct fc { ll a, c, b_cnt; } A[maxn], a[maxn];
inline bool can(ll x) {
for(int i = 0;i < m;++i) {
ll val = sub(mul(A[i].a, x), A[i].c);
if(val > err && val < mod - err) return 0;
}
return 1;
}
ll L, R;
inline int operator < (const fc & x, const fc & y) { return x.a < y.a; }
inline int operator == (const fc & x, const fc & y) { return x.a == y.a; }
std::vector<fc> vector;
inline bool mul_less(ll a, ll b, ll c) {
return (ld) a * b <= c * 1.1 && a * b <= c;
}
inline void update(ll a, ll c, ll b_cnt) {
if(mul_less(b_cnt, err * 2, a == 1 ? mod : mod / 2)) {
if(mul_less(R - L + 1, a, mod)) {
ll min = mul(L, a), max = mul(R, a);
if(max < min) max += mod;
ll range = b_cnt * err, min_can = c - range, max_can = c + range;
for(;min_can > max;) min_can -= mod, max_can -= mod;
for(;max_can < min;) min_can += mod, max_can += mod;
if(min_can + mod <= max || min <= max_can - mod) return ;
if(min_can > min) L += (min_can - min) / a;
if(max_can < max) R -= (max - max_can) / a;
}
}
}
inline void emplace(ll a, ll c, ll b_cnt) {
vector.push_back((fc) { a, c, b_cnt});
update(a, c, b_cnt);
}
inline void reduce() {
vector.clear();
ll det = rd() % mod;
int need = R - L < mod / 4;
if(need) L += det, R += det;
else L = 0, R = mod - 1;
for(int i = 0;i < m;++i) {
a[i] = A[i];
a[i].c = add(a[i].c, mul(a[i].a, det));
}
for(int i = 0;i < 20000;++i) {
ll A = 0, C = 0;
for(int j = 0, p[3];j < 3;++j) {
start:
int&which = p[j] = rd() % m;
for(int k = 0;k < j;++k) if(p[j] == p[k]) goto start;
if(rd() & 1) {
A = add(A, a[which].a);
C = add(C, a[which].c);
} else {
A = sub(A, a[which].a);
C = sub(C, a[which].c);
}
}
emplace(A, C, 3);
}
for(int i = 0;i < 5;++i) {
if(vector.size() > 3000) {
nth_element(vector.begin(), vector.begin() + 3000, vector.end());
vector.resize(3000);
}
sort(vector.begin(), vector.end());
vector.erase(unique(vector.begin(), vector.end()), vector.end());
for(int size = vector.size(), i = 0;i < size;++i) {
for(int j = i + 1;j < i + 10 && j < size;++j) {
emplace(vector[j].a - vector[i].a, sub(vector[j].c, vector[i].c), vector[i].b_cnt + vector[j].b_cnt);
}
}
}
L -= det, R -= det;
}
int main() {
// freopen("1.in", "r", stdin);
std::ios::sync_with_stdio(false), cin.tie(0);
cin >> T;
for(int i = 0;i < T;++i) {
cin >> m >> mod >> err;
err = err + 1 >> 1;
for(int i = 0;i < m;++i) {
cin >> A[i].a >> A[i].c;
A[i].b_cnt = 1;
}
L = 0, R = mod - 1;
for(;R - L > 5000;) {
reduce();
// std::cerr << L << ' ' << R << '
';
}
L = R = L + R >> 1;
for(;;-- L, ++ R) {
if(can(L)) { cout << (L + mod) % mod << std::endl; break; }
if(can(R)) { cout << (R + mod) % mod << std::endl; break; }
}
}
// std::cerr << double(clock()) / CLOCKS_PER_SEC << '
';
}