T281211 平地起高楼 题解+证明

提高组模拟赛二 T1,尽管做出来的人不少，但还是想要写一个证明

首先我们要知道

（曾经在 这里 写过）

不太严谨的证明：

（以下的“每一位”指的是二进制位）

我们知道 二进制数的每一位非 0 即 1 。

对于两个二进制数的每一位而言

按位或操作：这两个数中这一位有一个或两个为 1 ，这一位就为 1 。

按位与操作：这两个数中这一位有两个为 1 ，这一位就为 1 。

普通加法操作：这两个数中这一位有一个为 1 ，这一位就为 1 ；这两个数中这一位有两个为 1 ，这一位就为 2 。（暂时先不考虑进位）

换句话说 在求和时，按位或操作计算时有一个 1 的 计算了一次，但有两个 1 的 也只计算了一次，但是两个 1 的应该计算两次，所以再加上按位与即为两数之和。

（我表达能力有限，好像说的不是很清楚）

所以就变为了 或

很显然对于每一个可行的点，一定可以写成 的形式 （ 为任意整数），因为每一个点都是由另两个可行的点加或减得来的，最初是 和 ，所以每一个可行点都是 。

然后我们引出一个定理，叫做裴蜀定理。

（曾经在 这里 写过）

裴蜀定理得名于法国数学家艾蒂安·裴蜀，亦称贝祖定理。

1.裴蜀定理是指方程 有解，当且仅当 是 的倍数时，方程有整数解；

2.同时，一定存在整数 ，使 成立；

3.特别的，只有 和 互质时, 才有整数解。

极不严谨的证明：

方程两边同时除以

因为 且 ，所以 且 ，则

这里 表示 整除 ，即 能被 整除

通俗来说就是方程左边一定为整数，所以方程右边也一定为整数，所以 一定是 的倍数

所以每一个可行的点都能被 整除

可行的点的个数为 ，然后判断奇偶性即可

然后求 可以用欧几里得算法求解

（曾经在 这里 也写过）

古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。

欧几里得算法又称辗转相除法，一般用来求两个数的最大公约数，即

证明：

假设

设

则 可以表示成 ( 为正整数）

则 就等于

我们知道 ，则

因此 也是 和 的最大公因数

int gcd(int a,int b){return (b)?gcd(b,a%b):a;}

#include<algorithm>
using namespace std;
int a,b;
int main(){int c=__gcd(a,b);}

AC Code

#include<cstdio>
#include<algorithm>
using namespace std;
int T;long long n,x,y;
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%lld%lld%lld",&n,&x,&y);
        long long ans=n/__gcd(x,y);
        (ans&1)?puts("win"):puts("lose");
    }
    return 0;
}