CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

===== 题解 =====

首先题解中给出了一个可以除以二的操作序列：8k -> 15k -> 12k -> 5k -> 4k 。下面我们考虑把 $S$ 和 $T$ 都变成 $4$ 。

然后我们考虑一个勾股数的表示方法为 $(2pq,p^2-q^2,p^2+q^2)$ ，那么对于我们现在的 $2^{c}pq$ 可以用其变成 $2^{c+1}\frac{p+q}{2}\frac{p-q}{2}$ 。考虑再迭代一次就会变成 $2^{c+2}\frac{p}{2}\frac{q}{2}$ ，所以每操作两次至少能使得大的数减小一半。然后我们考虑在做的过程中每次把新的 $p,q$ 的 $2$ 的次幂提取出来，同时通过题解中的操作始终维持 $c$ 在一个较小的范围。这样一直做下去直到 $p=q=1$ ，我们就把 $c$ 通过题解的操作变成 $2$ 即可。

这里可能会遇到 $p=q$ 但是不是 $1$ 的情况。如果新的 $p,q$ 相等，那么我们对于原来的一定有 $(p+q)=2^k(p-q)$，进而就是 $q=\frac{2^k-1}{2^k+1}p$ ，于是我们只能令 $p=(2^k+1)*x$，然后新的数就是 $p=q=x$ ，然后这个x显然是不超过 $\frac{p}{3}$ 和 $q$ 的，所以相当于乘积除了一个 $3$ ，也至多只有 $log$ 次操作，变成 $x^2,1$ 继续处理即可。

ps：但是好像不加这个判断也能过，蛮怪的（

CVBB ACM Team

用户工具

站点工具

页面工具