2021CCPC华为云挑战赛-1006 仓颉造数

赛时没做出来，16:00结束当我推出大概结论的时候已经16:02了，这里还是打算把题解写一下，因为感觉官方题解概括性很强所以部分同学 （指我这个菜鸡） 可能看不懂，所以这里写一些自己的思路

另外因为HDUOJ挂了，大家看看题看看思路就好可以简单想想做法，（或者等HDU修好）

前方大量数学公式预警

传送门

题目大意

因为是中文题目，所以就不写了（咕）

解题思路

先说最终结论：对$\frac{a}{b}$约分后，若满足$a+b=2^m$，则能够合成$1$。
（官方题解有写，这里给出貌似也没啥用）
实际上那个999999999999比较大所以不用管天数……

下述证明过程中只使用了$\frac{x+y}{2}$，没有使用$\frac{2xy}{x+y}$，理由是：

$\frac{2xy}{x+y}等价于\frac{2}{\frac{1}{x}+\frac{1}{y}} \\ \ \\ 所以当我们要求出1时 \\ \ \\ 只需要x+y=2（由式1推得）或\frac{1}{x}+\frac{1}{y}=2（由式2推得）\\ \ \\ 而如果我们可以得出x，则一定也可以得到它的倒数\frac{1}{x}\\ \ \\ 原因是：我们得初值\frac{a}{b}和\frac{b}{a}互为倒数，\\ \ \\ 并且将其带入到式1和式2中会得到\frac{2ab}{a^2+b^2}和\frac{a^2+b^2}{2ab}也互为倒数\\ \ \\ 我们可以选择其中任意一个表达式选取我们所需要的结果$

首先证明下面一个结论：在任意一天，我们获得的数一定满足如下表达式（该表达式可以通过手算得到规律）

$\frac{xa^2+yb^2}{(x+y)ab}，其中x+y=2^m \\$

证明前同时给出该公式的另一表达形式，方便看懂后面的部分：

$\frac{xa^2+yb^2}{(x+y)ab}，其中x+y=2^m \\ \Rightarrow \frac{xa^2+(t-x)b^2}{tab}，其中x+y=2^m=t\\ \\$

证明：利用数学归纳法的思想

1. 在第0天的时候，$\frac{a}{b}$和$\frac{b}{a}$分别是上述表达式在$x=1,y=0$和$x=0,y=1$时的特例。

2. 在以后的某一天当中，我选取的任意两个数一定满足上述表达式，则

$\frac{\frac{x_1a^2+(t_1-x_1)b^2}{t_1ab} + \frac{x_2a^2+(t_2-x_2)b^2}{t_2ab}}{2}（计算两项之和）\\ \ \\ =\frac{x_1t_2a^2+(t_1t_2-x_1t_2)b^2+x_2t_1a^2+(t_1t_2-x_2t_1)b^2}{2t_1t_2ab}（通分）\\ \ \\ =\frac{(x_1t_2 + x_2t_1)a^2+(2t_1t_2-(x_1t_2+x_2t_1))b^2}{2t_1t_2ab} （合并同类型）\\ \ \\ 令X=x_1t_2 + x_2t_1,T=2t_1t_2，则上述表达式可以进一步化简为: \\ \ \\ \frac{Xa^2+(T-X)b^2}{Tab}(看上去就舒服多了) \\ \ \\ 而此时我们可以发现T=2t_1t_2=2·2^{m_1}·2^{m_2} = 2^{m_1+m_2+1}=X+Y\\ \ \\ 即新得到的表达式也满足条件$

综上，可以得出结论，得到的所有数字均满足上述表达式，证毕。

有了上述结论，我们就可以进行下一步的证明。
首先，初始获得的是数字$\frac{a}{b}$和$\frac{b}{a}$，我们先对其进行约分，后面的证明需要用到
a /= __gcd(a,b); b /= __gcd(a,b);

由于我的目的是合成1，所以让某一天获得的数字等于1即可，即对下面的表达式进行化简：

$\frac{xa^2+yb^2}{(x+y)ab} = 1\\ \ \\ \Rightarrow xa^2+yb^2-xab-yab=0 \\ \ \\ \Rightarrow x(a^2-ab) + y(b^2-ab)=0\\ \ \\ \Rightarrow (xa-yb)(a-b)=0 \\ \ \\ \Rightarrow a=b\ 或\ xa=yb \\ \ \\ a=b可以看成 xa=yb的特殊条件\\ \ \\ 有\frac{a}{b} = \frac{y}{x} \\ \ \\ 同时由于\frac{a}{b}为既约分数，且可以证明\frac{y}{x}也为既约分数（见下）\\ \ \\ 即可得到a=y，b=x \\ \ \\ 由于x+y=2^m，即a+b=2^m$

下面证明$\frac{y}{x}$为既约分数：

证明 ：

$若x,y含有2以外的公因子，这与x+y=2^m矛盾\\ 若x.y均为偶数，则在计算时就已经与x+y进行约分\\ 所以gcd(x,y)=1$

证毕。

至此全部证明结束。

AC代码

代码中用lowbit判断是否为2的幂次

#include <bits/stdc++.h>
typedef long long llong;
typedef unsigned long long ullong;
const int N = 1e5 + 5;
using namespace std;

int a, b;

int main() {
    #ifdef LOCAL
        freopen("E:/code/ACM/in.in", "r", stdin);
        freopen("E:/code/ACM/out.out", "w", stdout);
    #endif
    int T;    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &a, &b);
        int x = __gcd(a, b);
        a /= x; b /= x;
        puts((((a + b) & -(a + b)) == (a + b)) ? "Yes" : "No");
    }
    return 0;
}