差别
题目描述
给定 \(a,b,c,d\)，求 \(p,q,r,s\) 使得 \(M\) 成为非零最小值。
Solution
\(M\) 的表达式很复杂，把式子拆开有 \(16\) 个 \(4\) 次项，不难发现这是一个平方和，不断套平方和公式，最后化简成：
\[ M = |(ap+bq+cr-ds)^2 + (-aq+bp+cs+dr)^2| = ((a+bi) \times (p-qi) + (c+di) \times (r+si))^2。 \]这样就可以用 exgcd 求解，但如何在复数值域上求解 exgcd 呢？
考虑使用带余除法进行计算，设 \(\alpha = a+bi, \beta = c+di\)，则 \(\alpha = \varepsilon \beta + \gamma (\varepsilon, \gamma \in \mathbb{Z})\)，用内除法和外除法定义复数的除法，但得保证 \(N(\gamma) \le \frac{N(\beta}{2}\)（\(N(\alpha)\) 表示 \(\alpha\) 的范数即 \(|\alpha|^2\)）。
如何证明？
设 \(\gamma = p+qi = \frac{\alpha}{\beta}, \varepsilon = r+si(|r-p| \le \frac{1}{2}, |s-q| \le \frac{1}{2})\) 。
\(\therefore N (\gamma - \varepsilon) = (p-r)^ 2 + (q-s) ^ 2 \le \frac{1}{2}\) 。
\(\therefore \gamma = \alpha - \varepsilon \beta = (\gamma - \varepsilon) \times \beta\)。
\(\therefore N(\gamma) = N(\gamma - \varepsilon) \times N(\beta) \le \frac{1}{2} \times \beta\)，证毕。
所以令 \(\varepsilon = \left \lfloor \frac{\alpha}{\beta} \right \rfloor, \gamma = \alpha \bmod \beta\) 即可。
实际上代码上实现只需要 $\alpha - \frac{\alpha}{\beta} \times \beta $ 即可表示 \(\alpha \bmod \beta\)，最难的部分就是证明。
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll lread(ll x=0, bool f=0, char c=getchar()) {for(;!isdigit(c);c=getchar()) f^=!(c^45);for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);return f?-x:x;}
ll A, B, C, D, m;
struct plural
{
ll x, y;
plural () {}
plural (ll x, ll y) : x(x), y(y) {}
bool operator == (const plural &other) const {return (x == other.x) && (y == other.y);}
plural operator+(const plural &other) const {return plural(x+other.x, y+other.y);}
plural operator-(const plural &other) const {return plural(x-other.x, y-other.y);}
plural operator*(const plural &other) const {return plural(x*other.x - y*other.y, x*other.y + y*other.x);}
plural operator/(const plural &other) const {
double a = x, b = y, c = other.x, d = other.y, alpha = (a*c + b*d) / (c*c + d*d), beta = (b*c - a*d) / (c*c + d*d);
return plural(round(alpha), round(beta));
}
plural operator % (const plural &other) const {return (*this) - (*this) / other * other;}
};
void exgcd(plural a, plural b, plural &x, plural &y)
{
// cerr << b.x << " " << b.y << endl;
if(b == plural(0ll, 0ll)) return m = a.x * a.x + a.y * a.y, x = plural(1ll, 0ll), void();
exgcd(b, a%b, x, y);
plural tmp = x;
x = y, y = tmp - a/b*y;
}
int main()
{
A = lread(), B = lread(), C = lread(), D = lread();
plural alpha = plural(A, B), beta = plural(C, D), x, y;
exgcd(alpha, beta, x, y);
printf("%lld %lld %lld %lld %lld", x.x, -x.y, y.x, y.y, m);
}
Tips
记得开 long long。