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$ 。