为什么 n*(n+1)/2 % 2 在 if 条件下等价于按位运算 (n+1) & 2？

无卤 • • 问答

再次更新：抱歉放错了需要登录的链接...你现在可以看到代码了

更新：抱歉误导...已经编辑了标题

有一个问题：

但我想知道，为什么条件[n*(n+1)/2 % 2]可以替换为[(n+1) & 2]？

我在网站上看到这个

问题网站是：https : //cses.fi/problemset/task/1092

该代码在这里：https : //paste.ubuntu.com/p/GfVG9R67zj/

///2021-06-17 02:21:43  SchizoYoshi C++17   0.10 s
///paste from https://cses.fi/problemset/hack/1092/entry/2352488/
#include <iostream>
auto& c = std::cout;

int main() {
    int n, i{};
    std::cin >> n;
    if (++n & 2)
        c << "NO ";
 
    c << "YES " << n-- / 2 << ' ';
    while (n - i++)
        if (i - n & 2)
            c << i << ' ';
    c << n-- / 2 << ' ';
    while (--i)
        if (n - i & 2)
            c << i << ' ';
}

回答

n*(n+1)/2 % 2 == 0有效测试是否n或n+1可被 4 整除；是否可以被2整除两次。确实，有两种可能；如果n是偶数，则n+1是奇数，因此除以 2 两次的唯一方法是n被 4 整除。同样，如果n是奇数，则为偶数，n+1并且必须被 4 整除才能满足条件。

类似地，(n+1) & 2 == 0测试n或n+1是否可以被 4 整除。它测试 中的第二低位为零n+1。如果最低位也为零，则n+1可以被 4 整除（它看起来像X00二进制，因此可以右移两位而不产生进位）。如果 in 的最低位n+1是 1，则 in 的最低位n是 0，然后n是形式X00并且可以被 4 整除。

以上是为什么 n*(n+1)/2 % 2 在 if 条件下等价于按位运算 (n+1) &amp; 2？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>