自动搬运

查看原文

来自洛谷，原作者为

	max0810 刚刚上初一，正在学习数据结构，求大佬带

搬运于2025-08-24 22:39:59，当前版本为作者最后更新于2022-09-16 11:28:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

考试的时候在乱猜结论，交了几遍就过了，证明当然是赛后才想的（）

文中加粗部分是需要读者稍微思考一下原因的地方 （不是重点）。

---

先考虑一下样例二，将 $10^{18}$ 化成二进制：$1101...001000000000000000000$。

其实只需要知道末尾有 $18$ 个 $0$ 就行了，因为在 $x$ 变为 $x^{2c}$ 时，后面 $18$ 个 $0$ 就会变成 $18\times 2c$ 个 $0$，如果再异或 $c$，就相当于把末尾的几位变成 $c$，此时除了末尾上的 $c$，$x^{2c}\oplus c$ 的前面部分的数已经不会影响结果了（因为最后求 $\operatorname{lowbit}$ 就只关心末几位的值）。所以每做一次操作，末几位都是 $c$，那么最后的 $\operatorname{lowbit}$ 就是 $\operatorname{lowbit}(c)$。

再扩展到一般情况：

• $c$ 是偶数，$a$ 是奇数，那么二进制中的最后一位就始终都是 $1$，所以最后的 $\operatorname{lowbit}$ 就是 $1$。

• $c$ 是偶数，$a$ 是偶数，这个就和样例二差不多：$a$ 的二进制末尾至少有一个 $0$，$a^{2c}$ 的末尾就至少有 $2c$ 个 $0$，肯定比 $c$ 的二进制的位数多，异或 $c$ 就相当于把末尾的几位变成 $c$，又因为 $c$ 是偶数，所以 $a^{2c}\oplus c$ 的末尾也至少有一个 $0$，又变成了开始的情况，只不过末几位是 $c$ 而不是 $a$。一直推下去，最后的 $\operatorname{lowbit}$ 就是 $\operatorname{lowbit}(c)$。

• $c$ 是奇数，此时根据 $a$ 的奇偶又分成两种情况：

  • $a$ 是偶数，和前面一样：$a^{2c}$ 的末尾至少有 $2c$ 个 $0$，异或 $c$ 就相当于把末尾的几位变成 $c$，因为我们只关心末几位，所以就可以把原数看成 $c$。
  • $a$ 是奇数，那么 $a^{2c}$ 也是奇数，因为 $c$ 也是奇数，奇数异或奇数就变成了偶数，然后又变成了上一个情况，即奇偶交替。
  • 如果最后的数是个奇数，那么 $\operatorname{lowbit}$ 就是 $1$。
  • 如果最后是个偶数，那么就要考虑倒数第二步。因为 $b>1$，所以倒数第二步的数的二进制末尾一定是 $c$，那么最后答案就相当于 $\operatorname{lowbit}(c^{2c}\oplus c)$。

其实做到这就已经做完了，但是 $\operatorname{lowbit}(c^{2c}\oplus c)$ 还可以化简一下。

考虑用二项式定理展开 $c^{2c}$：

$$c^{2c}=(c-1+1)^{2c}=\sum_{i=0}^{2c} C_{2c}^{i}\times (c-1)^i=1+2c(c-1)+C_{2c}^{2}\times (c-1)^2+...+(c-1)^{2c} $$

我们将上式所有项按 $\operatorname{lowbit}$ 大小来排序，最小的两项当然是 $1$ 和 $2c(c-1)$，因为 $c-1$ 是偶数，所以 $\operatorname{lowbit}(2c(c-1))=\operatorname{lowbit}(c-1)\times 2$

从第三项开始，所有项的 $\operatorname{lowbit}$ 都不小于 $\operatorname{lowbit}(c-1)\times 2$，所以 $c^{2c}$ 一定可以被表示为 $k\times \operatorname{lowbit}(2(c-1))+1$，其中 $k\in N^+$。

形象点，把 $c^{2c}$ 和 $c$ 的二进制分别表示出来（随便一个例子，只需要看后五位）：

$c^{2c}$：$1101...1010001$

$c$： $\ \ 1010...0101001$

可以发现，最末尾的 $1$ 会抵消，但倒数第二位不会，所以 $\operatorname{lowbit}(c^{2c}\oplus c)=\operatorname{lowbit}(c-1)$。

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
ll a,b,c;
ll lb(ll x){return x&-x;}
int main()
{
    cin >> a >> b >> c;
    if(c&1)
    {
        if((a&1)^(b&1))cout << 1; //ab不同奇偶，那么最后答案就是奇数
        else cout << lb(c-1); //ab同奇偶，最后答案就是偶数
    }
    else cout << ((a&1)?1:lb(c));
    return 0;
}