自动搬运

查看原文

来自洛谷，原作者为

	Daniel13265 **

搬运于2025-08-24 22:19:28，当前版本为作者最后更新于2020-03-22 14:09:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

这是「Daniel13265 的公开赛」的官方题解。

---

测试点 $1$

$$M=\left(a^2+b^2\right)\left(p^2+q^2\right).$$

令 $p=1,q=r=s=0$ 即可，此时 $M=a^2+b^2$。

测试点 $2$

$$\begin{aligned}M&=\Big|b^2\left(p^2+q^2\right)+d^2\left(r^2+s^2\right)+2bd\big(pr-qs\big)\Big|\\&=\Big|\big(b^2p^2+d^2r^2+2bdpr\big)+\big(b^2q^2+d^2s^2-2bdqs\big)\Big|\\&=\Big|(bp+dr)^2+(bq-ds)^2\Big|\\&=(bp+dr)^2+(bq-ds)^2.\end{aligned} $$

故有 $\gcd^2(b,d)|M$ 。

令 $q=s=0$ ，则只要找出两个整数 $p,r$ 使得 $bp+dr=\gcd(b,d)$ ，直接使用扩展欧几里得算法即可。此时 $M=\gcd^2(b,d)$ 。

测试点 $3$

$$M=\Big|a^2\left(p^2+q^2\right)+c^2\left(r^2+s^2\right)+2ac\big(pr-qs\big)\Big|. $$

与测试点 $2$ 相同，略。

测试点 $4$

设 $b=ka,d=kc$ ，则有

$$\begin{aligned}M&=\big(ap+cr\big)^2+\big(aq-cs\big)^2+\big(bq-ds\big)^2+\big(bp+dr\big)^2\\&=\big(k^2+1\big)\Big[(ap+cr\big)^2+\big(aq-cs\big)^2\Big].\end{aligned} $$

同测试点 $2$ ，略。

测试点 $5$

猜测 $|p|,|q|,|r|,|s|\leq10$ ，直接枚举即可。

测试点 $6\sim10$

$$\begin{aligned}M&=\Big|(bq-ds)^2+(bp+dr)^2+(ap+cr)^2+(-aq+cs)^2+2(bc-ad)(ps+qr)\Big|\\&=\Big|(ap+bq+cr-ds)^2+(-aq+bp+cs+dr)^2\Big|\\&=(ap+bq+cr-ds)^2+(-aq+bp+cs+dr)^2.\end{aligned} $$

构造复数 $A=a+bi,x=p-qi,B=c+di,y=r+si$ ，则 $M=\big|Ax+By\big|^2$，使用扩展欧几里得算法求解即可。如果认为 $|a|,|b|,|c|,|d|$ 同阶，时间复杂度为 $\mathcal O\left(\log|a|\right)$。

另外，观察大样例猜测到 $M=\gcd\left(a^2+b^2,c^2+d^2,2|ac+bd|,2|bc-ad|\right)$ 可以得到每个测试点 $40\%$ 的分数。

补充：高斯整数的扩展欧几里得算法

由于题解界面中希腊字母的渲染实在称不上好看，因此建议此部分到博客中查看。

---

定义（范数）

$\alpha=a+bi\in\mathbb Q[i]$ 的范数 $N(\alpha)=a^2+b^2=|\alpha|^2$。

一个引理

对于 $\alpha,\beta\in\mathbb Q[i]$，有 $N(\alpha\beta)=N(\alpha)N(\beta)$。

证明： 设 $\alpha=p+qi,\beta=r+si$，则

$$\begin{aligned}N(\alpha\beta)&=(pr-qs)^2+(ps+qr)^2\\&=p^2r^2+p^2s^2+q^2r^2+q^2s^2\\&=\left(p^2+q^2\right)\left(r^2+s^2\right)\\&=N(\alpha)N(\beta)\end{aligned} $$

定理（带余除法）

对于 $\alpha,\beta\in\mathbb Z[i],\alpha\neq0$，一定存在 $\eta,\gamma\in\mathbb Z[i]$ 使得

$$\beta=\eta\alpha+\gamma,\qquad0\le N(\gamma)\leq\frac12N(\alpha) $$

证明： 设 $\tau=p+qi=\dfrac\beta\alpha\in\mathbb Q[i]$，取 $r,s\in\mathbb Z$ 且 $|p-r|\le\dfrac12,|q-s|\le\dfrac12$，取 $\eta=r+si$，则有

$$N(\tau-\eta)=(p-r)^2+(q-s)^2\le\dfrac12$$

因为 $\gamma=\beta-\eta\alpha=(\tau-\eta)\alpha$，所以由上面的引理有

$$N(\gamma)=N(\tau-\eta)N(\alpha)\le\frac12N(\alpha) $$

因此，仿照整数记 $\eta=\left\lfloor\dfrac\beta\alpha\right\rfloor,\gamma=\beta\mod\alpha$，于是就可以使用扩展欧几里得算法了。

由于作一次除法时范数将减小至少一半，因此复数域的扩展欧几里得算法的时间复杂度为 $\mathcal O\left(\log N(\alpha)\right)$。