差别 - 题目列表

题意

给定 a,b,c,d，要求找到一组整数 p,q,r,s，使下面这个值的非零最小值尽量小：

M = | ... |

注意输出顺序是：

p q r s M

也就是最小值 M 在最后。

思路

先看一个最直接的小数据暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128_t;

const int LIM = 12;

struct Answer {
    i64 p, q, r, s;
    i128 m;
};

string to_string_i128(i128 x) {
    if (x == 0) {
        return "0";
    }

    bool neg = false;
    if (x < 0) {
        neg = true;
        x = -x;
    }

    string s;
    while (x > 0) {
        int digit = (int) (x % 10);
        s.push_back(char('0' + digit));
        x /= 10;
    }
    if (neg) {
        s.push_back('-');
    }
    reverse(s.begin(), s.end());
    return s;
}

i128 calc_value(i64 a, i64 b, i64 c, i64 d, i64 p, i64 q, i64 r, i64 s) {
    // M = |(a+bi)(p-qi) + (c+di)(r+si)|^2
    i128 real_part = (i128) a * p + (i128) b * q + (i128) c * r - (i128) d * s;
    i128 imag_part = (i128) b * p - (i128) a * q + (i128) c * s + (i128) d * r;
    return real_part * real_part + imag_part * imag_part;
}

bool better_answer(const Answer &a, const Answer &b) {
    if (a.m != b.m) return a.m < b.m;
    if (a.p != b.p) return a.p > b.p;
    if (a.q != b.q) return a.q > b.q;
    if (a.r != b.r) return a.r > b.r;
    return a.s > b.s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 a, b, c, d;
    cin >> a >> b >> c >> d;

    Answer best = {0, 0, 0, 0, -1};
    bool found = false;

    // 只用于小数据验证：直接枚举 p, q, r, s。
    for (i64 p = -LIM; p <= LIM; p++) {
        for (i64 q = -LIM; q <= LIM; q++) {
            for (i64 r = -LIM; r <= LIM; r++) {
                for (i64 s = -LIM; s <= LIM; s++) {
                    i128 now = calc_value(a, b, c, d, p, q, r, s);
                    if (now == 0) {
                        continue;
                    }

                    Answer cur = {p, q, r, s, now};
                    if (!found || better_answer(cur, best)) {
                        found = true;
                        best = cur;
                    }
                }
            }
        }
    }

    cout << best.p << ' '
         << best.q << ' '
         << best.r << ' '
         << best.s << ' '
         << to_string_i128(best.m) << '\n';

    return 0;
}

暴力版就是在一个很小的范围里枚举 p,q,r,s，直接代公式算出 M。
这当然只能用来帮助理解和对拍，根本不可能应付正式数据。

这题真正的关键，是把那个长式子认成一个高斯整数范数。

设：

A = a + bi
B = c + di
X = p - qi
Y = r + si

那么原式恰好就是：

M = |A X + B Y|^2

也就是说，我们实际上是在问：

A X + B Y 能取到的非零复整数里，范数最小的是谁

而高斯整数环是欧几里得整环，所以由 A 和 B 生成的所有线性组合：

A X + B Y

构成一个主理想，它由高斯整数 gcd 生成。

于是最小非零范数，正好就是：

gcd(A, B) 的范数

这张图表达的就是这个关系：

flowchart LR
  A["所有线性组合 A·X+B·Y"] --> B["形成一个高斯整数理想"]
  B --> C["这个理想由 gcd(A,B) 生成"]
  C --> D["最小非零 M = |gcd(A,B)|^2"]

图里真正重要的是：
我们不再直接找 p,q,r,s，而是先去找高斯整数里的 gcd。
一旦求出了贝祖系数：

A X + B Y = g

就能直接从 X,Y 反推出 p,q,r,s。

还有一个实现细节：
高斯整数 gcd 只差一个单位元 ±1, ±i 都是同一个答案。
为了让本地样例输出稳定，代码里会把这 4 组等价答案都试一遍，固定选字典序最大的那组输出。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using i128 = __int128_t;

struct GaussInt {
    i128 x, y; // x + yi
};

struct Answer {
    i128 p, q, r, s;
};

GaussInt operator + (const GaussInt &a, const GaussInt &b) {
    return {a.x + b.x, a.y + b.y};
}

GaussInt operator - (const GaussInt &a, const GaussInt &b) {
    return {a.x - b.x, a.y - b.y};
}

GaussInt operator * (const GaussInt &a, const GaussInt &b) {
    return {
        a.x * b.x - a.y * b.y,
        a.x * b.y + a.y * b.x
    };
}

bool is_zero(const GaussInt &a) {
    return a.x == 0 && a.y == 0;
}

i128 norm(const GaussInt &a) {
    return a.x * a.x + a.y * a.y;
}

string to_string_i128(i128 x) {
    if (x == 0) {
        return "0";
    }

    bool neg = false;
    if (x < 0) {
        neg = true;
        x = -x;
    }

    string s;
    while (x > 0) {
        int digit = (int) (x % 10);
        s.push_back(char('0' + digit));
        x /= 10;
    }
    if (neg) {
        s.push_back('-');
    }
    reverse(s.begin(), s.end());
    return s;
}

// 把 a / b 四舍五入到最近的整数。
i128 round_div(i128 a, i128 b) {
    if (a >= 0) {
        return (a + b / 2) / b;
    }
    return -((-a + b / 2) / b);
}

// 高斯整数带余除法：a = bq + r，且 r 的范数足够小。
GaussInt gauss_div(const GaussInt &a, const GaussInt &b) {
    i128 den = norm(b);
    i128 real_up = a.x * b.x + a.y * b.y;
    i128 imag_up = a.y * b.x - a.x * b.y;
    return {
        round_div(real_up, den),
        round_div(imag_up, den)
    };
}

// 返回 gcd(a, b)，并求出 ax + by = gcd(a, b) 的一组贝祖系数。
GaussInt exgcd(const GaussInt &a, const GaussInt &b, GaussInt &x, GaussInt &y) {
    if (is_zero(b)) {
        x = {1, 0};
        y = {0, 0};
        return a;
    }

    GaussInt q = gauss_div(a, b);
    GaussInt r = a - q * b;

    GaussInt x1, y1;
    GaussInt g = exgcd(b, r, x1, y1);

    x = y1;
    y = x1 - q * y1;
    return g;
}

GaussInt mul_unit(const GaussInt &a, int type) {
    if (type == 0) return a;             // 1
    if (type == 1) return {-a.x, -a.y}; // -1
    if (type == 2) return {-a.y, a.x};  // i
    return {a.y, -a.x};                 // -i
}

Answer decode_answer(const GaussInt &u, const GaussInt &v) {
    // 原式可以写成：
    // M = |(a+bi)(p-qi) + (c+di)(r+si)|^2
    return {u.x, -u.y, v.x, v.y};
}

bool better_answer(const Answer &a, const Answer &b) {
    if (a.p != b.p) return a.p > b.p;
    if (a.q != b.q) return a.q > b.q;
    if (a.r != b.r) return a.r > b.r;
    return a.s > b.s;
}

Answer normalize_answer(const GaussInt &u, const GaussInt &v) {
    bool first = true;
    Answer best = {0, 0, 0, 0};

    // 同乘一个单位元 ±1、±i，不会改变最小范数。
    // 为了让本地样例输出稳定，这里固定选字典序最大的那一组。
    for (int type = 0; type < 4; type++) {
        GaussInt nu = mul_unit(u, type);
        GaussInt nv = mul_unit(v, type);
        Answer cur = decode_answer(nu, nv);
        if (first || better_answer(cur, best)) {
            first = false;
            best = cur;
        }
    }

    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    i64 a, b, c, d;
    cin >> a >> b >> c >> d;

    GaussInt A = {(i128) a, (i128) b};
    GaussInt B = {(i128) c, (i128) d};

    GaussInt u, v;
    GaussInt g = exgcd(A, B, u, v);

    Answer ans = normalize_answer(u, v);
    i128 M = norm(g);

    cout << to_string_i128(ans.p) << ' '
         << to_string_i128(ans.q) << ' '
         << to_string_i128(ans.r) << ' '
         << to_string_i128(ans.s) << ' '
         << to_string_i128(M) << '\n';

    return 0;
}

复杂度

高斯整数 exgcd 的复杂度和普通 exgcd 类似，取决于欧几里得算法的轮数。
在本题数据范围内可以看作对数级。

空间复杂度：

$O(1)$

总结

这题最难的地方不是实现，而是第一眼认公式。

一旦看出：

M = |(a+bi)(p-qi) + (c+di)(r+si)|^2

后面就变成一题高斯整数 gcd / 贝祖系数模板题了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

测试点编号	特殊性质
$1$	$c=d=0$
$2$	$a=c=0$
$3$	$b=d=0$
$4$	$ad=bc$
$5$	$\vert a\vert,\vert b\vert,\vert c\vert,\vert d\vert\le10$
$6\sim10$	无

差别

目录

题意

思路

代码

复杂度

总结

一图流解析