「Daniel13265 的公开赛」题解【差别】

· · 题解

这是「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,\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)$。