HDU-7092 仓颉造数

题目大意，给定两个数字 a b , b a \frac{a}{b},\frac{b}{a} ba​,ab​，每次选取两个数字 x , y x,y x,y合称为 x + y 2 \frac{x + y}{2} 2x+y​或 2 x y x + y \frac{2xy}{x + y} x+y2xy​，合成后原来的两个数字仍然存在，求是否能够经过有限次合成得到数字 1 1 1。

首先，我们分析每次可以合成的两个数字 x + y 2 \frac{x + y}{2} 2x+y​或 2 x y x + y \frac{2xy}{x + y} x+y2xy​，后者即为 2 1 x + 1 y \frac{2}{\frac1x + \frac1y} x1​+y1​2​，再找到最后一步合成 1 1 1时的状态：一定有 x + y 2 = 1 \frac{x + y}{2} = 1 2x+y​=1或 2 1 x + 1 y = 1 \frac{2}{\frac1x + \frac1y}=1 x1​+y1​2​=1，即为 x + y = 2 x + y = 2 x+y=2或 1 x + 1 y = 2 \frac1x + \frac1y = 2 x1​+y1​=2。

而我们初始状态下给定的 a b \frac{a}{b} ba​和 b a \frac{b}{a} ab​，这两个数字互为倒数，我们将其代入两个合成的公式，可以得到 2 a b a 2 + b 2 \frac{2ab}{a^2 + b^2} a2+b22ab​和 a 2 + b 2 2 a b \frac{a^2 + b ^2}{2ab} 2aba2+b2​两个数字，可以发现这两个数字互为倒数。也就是说我们可以得到一个数字 m m m，那么也一定能得到 1 m \frac1m m1​。

打表可以发现：在任意一天，无论选取哪两个数合成，我们获得的数字一定满足如下表达式： m a 2 + n b 2 ( m + n ) a b ， 其 中 m + n = 2 n \frac{ma^2 + nb^2}{(m + n)ab}，其中m + n = 2^n (m+n)abma2+nb2​，其中m+n=2n (关于打的表可以去看dalao的博客：hdu 7092 仓颉造数 （猜测，手模数据找规律，推公式）_yezzz的博客-CSDN博客)

于是我们尝试证明该结论：

假设要合成的两个数为 m 1 a 2 + n 1 b 2 ( m 1 + n 1 ) a b , m 2 a 2 + n 2 b 2 ( m 2 + n 2 ) a b \frac{m_1a^2 + n_1b^2}{(m_1 + n_1)ab}, \frac{m_2a^2 + n_2b^2}{(m_2 + n_2)ab} (m1​+n1​)abm1​a2+n1​b2​,(m2​+n2​)abm2​a2+n2​b2​，则 m 1 a 2 + n 1 b 2 ( m 1 + n 1 ) a b + m 2 a 2 + n 2 b 2 ( m 2 + n 2 ) a b 2 = m 1 m 2 a 2 + n 1 n 2 b 2 + m 1 n 2 a 2 + m 2 n 1 b 2 + m 1 m 2 a 2 + n 1 n 2 b 2 + m 2 n 1 a 2 + m 1 n 2 b 2 2 ( m 1 + n 1 ) ( m 2 + n 2 ) a b = 2 m 1 m 2 a 2 + 2 n 1 n 2 b 2 + ( m 1 n 2 + m 2 n 1 ) a 2 + ( m 1 n 2 + m 2 n 1 ) b 2 2 ( m 1 + n 1 ) ( m 2 + n 2 ) a b = ( m 1 n 2 + m 2 n 1 + 2 m 1 m 2 ) a 2 + ( m 1 n 2 + m 2 n 1 + 2 n 1 n 2 ) b 2 2 ( m 1 + n 1 ) ( m 2 + n 2 ) a b \begin{aligned} &\frac{\frac{m_1a^2 + n_1b^2}{(m_1 + n_1)ab} + \frac{m_2a^2 + n_2b^2}{(m_2 + n_2)ab}}{2}\\ =&\frac{m_1m_2a^2 + n_1n_2b^2 + m_1n_2a^2 + m_2n_1b^2 + m_1m_2a^2 + n_1n_2b^2 + m_2n_1a^2 + m_1n_2b^2}{2(m_1 + n_1)(m_2 + n_2)ab} \\ =&\frac{2m_1m_2a^2 + 2n_1n_2b^2 + (m_1n_2 + m_2n_1)a^2 + (m_1n_2 + m_2n_1)b^2 }{2(m_1 + n_1)(m_2 + n_2)ab} \\ =&\frac{(m_1n_2 + m_2n_1 + 2m_1m_2)a^2 + (m_1n_2 + m_2n_1 + 2n_1n_2)b^2}{2(m_1 + n_1)(m_2 + n_2)ab} \\ \end{aligned} ===​2(m1​+n1​)abm1​a2+n1​b2​+(m2​+n2​)abm2​a2+n2​b2​​2(m1​+n1​)(m2​+n2​)abm1​m2​a2+n1​n2​b2+m1​n2​a2+m2​n1​b2+m1​m2​a2+n1​n2​b2+m2​n1​a2+m1​n2​b2​2(m1​+n1​)(m2​+n2​)ab2m1​m2​a2+2n1​n2​b2+(m1​n2​+m2​n1​)a2+(m1​n2​+m2​n1​)b2​2(m1​+n1​)(m2​+n2​)ab(m1​n2​+m2​n1​+2m1​m2​)a2+(m1​n2​+m2​n1​+2n1​n2​)b2​​ 设 m 1 + n 1 = 2 N 1 ,   m 2 + n 2 = 2 N 2 m_1 + n_1 = 2^{N_1},\ m_2 + n_2 = 2^{N_2} m1​+n1​=2N1​, m2​+n2​=2N2​(其实不需要设 2 N 2^N 2N也能证明)，则： 2 ( m 1 + n 1 ) ( m 2 + n 2 ) = 2 N 1 + N 2 + 1 2(m_1 + n_1)(m_2 + n_2) = 2^{N_1 + N_2 + 1} 2(m1​+n1​)(m2​+n2​)=2N1​+N2​+1，检验分子系数： ( m 1 n 2 + m 2 n 1 + 2 m 1 m 2 ) + ( m 1 n 2 + m 2 n 1 + 2 n 1 n 2 ) = ( m 1 n 2 + m 1 m 2 + m 2 n 1 + m 1 m 2 ) + ( m 1 n 2 + n 1 n 2 + m 2 n 1 + n 1 n 2 ) = m 1 ( m 2 + n 2 ) + n 1 ( m 2 + n 2 ) + m 2 ( m 1 + n 1 ) + n 2 ( m 1 + n 1 ) = ( m 1 + n 1 ) ( m 2 + n 2 ) + ( m 2 + n 2 ) ( m 1 + n 1 ) = 2 N 1 × 2 N 2 × 2 = 2 N 1 + N 2 + 1 \begin{aligned} &(m_1n_2 + m_2n_1 + 2m_1m_2) + (m_1n_2 + m_2n_1 + 2n_1n_2)\\ =&(m_1n_2 + m_1m_2 + m_2n_1 + m_1m_2) + (m_1n_2 + n_1n_2 + m_2n_1 + n_1n_2)\\ =&m_1(m_2 + n_2) + n_1(m_2 + n_2) + m_2(m_1 + n_1) + n_2(m_1 + n_1) \\ =&(m_1 + n_1)(m_2 + n_2) + (m_2 +n_2)(m_1 + n_1) \\ =&2^{N_1} \times 2^{N_2} \times 2\\ =&2^{N_1 + N_2 + 1} \end{aligned} =====​(m1​n2​+m2​n1​+2m1​m2​)+(m1​n2​+m2​n1​+2n1​n2​)(m1​n2​+m1​m2​+m2​n1​+m1​m2​)+(m1​n2​+n1​n2​+m2​n1​+n1​n2​)m1​(m2​+n2​)+n1​(m2​+n2​)+m2​(m1​+n1​)+n2​(m1​+n1​)(m1​+n1​)(m2​+n2​)+(m2​+n2​)(m1​+n1​)2N1​×2N2​×22N1​+N2​+1​ 于是假设得证。

那么我们可以继续往下推，最后一步也一定满足这个式子，即为： m a 2 + n b 2 ( m + n ) a b = 1 ， 其 中 m + n = 2 N ， N > 0 \frac{ma^2 + nb^2}{(m + n)ab} = 1，其中m + n = 2^N，N>0 (m+n)abma2+nb2​=1，其中m+n=2N，N>0 即为： m a 2 + n b 2 − m a b − n a b = 0 ma^2 + nb^2-mab - nab = 0 ma2+nb2−mab−nab=0

化简： m a 2 + n b 2 − m a b − n a b = m ( a 2 − a b ) + n ( b 2 − a b ) = ( m a − n b ) × ( a − b ) = 0 \begin{aligned} &ma^2 + nb^2 - mab - nab \\ =&m(a^2 - ab) + n(b^2 - ab) \\ =&(ma - nb) \times(a - b) \\ =&0 \end{aligned} ===​ma2+nb2−mab−nabm(a2−ab)+n(b2−ab)(ma−nb)×(a−b)0​ 可得： a = b 或 m a = n b a = b 或 ma = nb a=b或ma=nb，由于 m , n m,n m,n可以取1，因此解可以认为只有 m a = n b ma = nb ma=nb一种形式。

即为 a b = n m \frac{a}{b} = \frac{n}{m} ba​=mn​。如果要使 a = n , b = m a = n,b = m a=n,b=m，则要求 a b \frac{a}{b} ba​最简(参考“既约分数”)。假设我们已经通分完毕，此时满足 a = n , b = m a = n,b = m a=n,b=m。又因为 x + y = 2 N x + y = 2^N x+y=2N，因此 a + b = 2 N a + b = 2^N a+b=2N。

#include 
#define int long long
using namespace std;

signed main(){
    int t; cin >> t;
    while (t--){
        int a, b; cin >> a >> b;
        a = (a + b) / __gcd(a, b);
        while (a % 2 == 0) a >>= 1;
        if (a == 1) cout