你们都这么求 Nimber 逆的？

· · 个人记录

别告诉我你 Nim 逆/Nim 开根还在快速幂。。。

定理 . 给定 a<[2^{2^k}]，存在 O(3^k) 的算法计算 a^2。

证明 . k=0 显然。若 k\ge1，设 B=[2^{2^{k-1}}],\beta=[2^{2^{k-1}-1}]。设 a=[pB+q]=pB+q，则 a^2=p^2B^2+q^2=p^2(B+\beta)+q^2。递归调用平方，计算 \beta 乘即可。

定理 . 给定非零 a<[2^{2^k}]，存在 O(k3^k) 的算法计算 a^{-1}。

证明 . k=0 显然。若 k\ge 1，设 B=[2^{2^{k-1}}],\beta=[2^{2^{k-1}-1}]。设 a=[pB+q]=pB+q，则 \dfrac1a=\dfrac1{pB+q}=\dfrac{pB+p+q}{(pB+q)(pB+p+q)}=\dfrac{pB+p+q}{p^2\beta+(p+q)q}。分母显然在 B 内。调用一次平方、一次乘法、一次 \beta 乘、递归求逆元、再两次乘法即可（注意 pB 和 p+q 可以分别乘这个逆元）。

定理 . 给定 k，存在 O(k) 的算法计算 \sqrt{[2^{2^k-1}]}。

证明 . 不难归纳得出答案为 [2^{2^k-1}]+\sum\limits_{i=0}^{k-1}[2^{2^k-1-2^i}]。

定理 . 给定 k，存在 O(k) 的算法计算 \sqrt{[2^{2^k}]}。

证明 . \sqrt{[2^{2^k}]}=\sqrt{[2^{2^k}]^2+[2^{2^k-1}]}=2^{2^k}+\sqrt{[2^{2^k-1}]} 即证。

定理 . 给定 k,a<[2^{2^k}]，存在 O(3^k) 的算法计算 a\sqrt{[2^{2^k-1}]}。

证明 . 若 k=0 显然。若 k\ge 1，设 \alpha=[2^{2^k-1}],B=[2^{2^{k-1}}],\beta=[2^{2^{k-1}-1}]。设 a=[pB+q]=pB+q，则 a\sqrt\alpha=(pB+q)\sqrt B\sqrt \beta=(pB+q)(B\sqrt \beta+\beta)=(p\beta+(p+q)\sqrt\beta)B+(p\sqrt\beta+q)\beta，调用两次自己，两次 \beta 乘即可。

定理 . 给定 a<[2^{2^k}]，存在 O(3^k) 的算法计算 \sqrt a。

证明 . 若 k=0 显然。若 k\ge 1，设 B=[2^{2^{k-1}}],\beta=[2^{2^{k-1}-1}]。设 a=[pB+q]=pB+q，则 \sqrt a=\sqrt{pB+q}=\sqrt p\sqrt B+\sqrt q=\sqrt p(B+\sqrt \beta)+\sqrt q，调用两次自己，再调用 \sqrt\beta 乘即可。