题目大意，给定两个数字 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+y12，再找到最后一步合成 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+y12=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)abm1a2+n1b2,(m2+n2)abm2a2+n2b2，则
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)abm1a2+n1b2+(m2+n2)abm2a2+n2b22(m1+n1)(m2+n2)abm1m2a2+n1n2b2+m1n2a2+m2n1b2+m1m2a2+n1n2b2+m2n1a2+m1n2b22(m1+n1)(m2+n2)ab2m1m2a2+2n1n2b2+(m1n2+m2n1)a2+(m1n2+m2n1)b22(m1+n1)(m2+n2)ab(m1n2+m2n1+2m1m2)a2+(m1n2+m2n1+2n1n2)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}
=====(m1n2+m2n1+2m1m2)+(m1n2+m2n1+2n1n2)(m1n2+m1m2+m2n1+m1m2)+(m1n2+n1n2+m2n1+n1n2)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
关注
打赏
![]()
查看更多评论
- 回坑记之或许是退役赛季？
- [LCT刷题] P1501 [国家集训队]Tree II
- [LCT刷题] P2147 洞穴勘测
- 2022-2023 ICPC Brazil Subregional Programming Contest VP记录
- [线段树套单调栈] 2019-2020 ICPC Asia Hong Kong Regional Contest H.[Hold the Line]
- The 2021 ICPC Asia Nanjing Regional Contest E.Paimon Segment Tree 区间合并线段树/维护矩阵乘法
- CF580E - Kefa and Watch 线段树维护哈希
- HDU5869 Different GCD Subarray Query 离线查询/区间贡献
- 27.CF1004F Sonya and Bitwise OR 区间合并线段树
- 26.CF1000F One Occurrence
