https://www.luogu.com.cn/problem/P1226
https://www.luogu.com.cn/problem/P3383
https://www.luogu.com.cn/problem/P3811
https://www.luogu.com.cn/problem/P1939
https://www.luogu.com.cn/problem/P3390
https://www.luogu.com.cn/problem/P4549
https://www.luogu.com.cn/problem/P5431
https://www.luogu.com.cn/problem/P2613
https://www.luogu.com.cn/problem/P5656
https://www.luogu.com.cn/problem/P1495
https://www.luogu.com.cn/problem/P4525

位运算

位运算就是基于整数的二进制表示进行的运算。由于计算机内部就是以二进制来存储数据，位运算是相当快的。

基本的位运算共 6 种，分别为按位与、按位或、按位异或、按位取反、左移和右移。

为了方便叙述，下文中省略“按位”。

与、或、异或¶

这三者都是两数间的运算，因此在这里一起讲解。

它们都是将两个整数作为二进制数，对二进制表示中的每一位逐一运算。

取反¶

取反是对一个数进行的位运算，即单目运算。

取反暂无默认的数学符号表示，其对应的运算符为 ~。它的作用是把的二进制补码中的和全部取反（变为，变为）。有符号整数的符号位在 ~ 运算中同样会取反。

补码：在二进制表示下，正数和的补码为其本身，负数的补码是将其对应正数按位取反后加一。

举例（有符号整数）：

左移和右移¶

复合赋值位运算符¶

和 += , -= 等运算符类似，位运算也有复合赋值运算符： &= , |= , ^= , <<= , >>= 。（取反是单目运算，所以没有。）

关于优先级¶

位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符（详见运算页面），所以使用时需多加注意，在必要时添加括号。

位运算的应用¶

位运算一般有三种作用：

高效地进行某些运算，代替其它低效的方式。
表示集合。（常用于状压 DP 。）
题目本来就要求进行位运算。

需要注意的是，用位运算代替其它运算方式（即第一种应用）在很多时候并不能带来太大的优化，反而会使代码变得复杂，使用时需要斟酌。（但像“乘 2 的非负整数次幂”和“除以 2 的非负整数次幂”就最好使用位运算，因为此时使用位运算可以优化复杂度。）

有关 2 的幂的应用¶

由于位运算针对的是变量的二进制位，因此可以推广出许多与 2 的整数次幂有关的应用。

将一个数乘（除） 2 的非负整数次幂：

// C++ Version
int mulPowerOfTwo(int n, int m) {  // 计算 n*(2^m)
  return n << m;
}
int divPowerOfTwo(int n, int m) {  // 计算 n/(2^m)
  return n >> m;
}

# Python Version
def mulPowerOfTwo(n, m): # 计算 n*(2^m)
    return n << m
def divPowerOfTwo(n, m): # 计算 n/(2^m)
    return n >> m

Warning

我们平常写的除法是向 0 取整，而这里的右移是向下取整（注意这里的区别），即当数大于等于 0 时两种方法等价，当数小于 0 时会有区别，如： -1 / 2 的值为0 ，而 -1 >> 1 的值为**-1** 。

取绝对值¶

在某些机器上，效率比 n > 0 ? n : -n 高。

// C++ Version
int Abs(int n) {
  return (n ^ (n >> 31)) - (n >> 31);
  /* n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1
     若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1)
     需要计算 n 和 -1 的补码，然后进行异或运算，
     结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值 */
}

# Python Version
def Abs(n):
    return (n ^ (n >> 31)) - (n >> 31)
    """
    n>>31 取得 n 的符号，若 n 为正数，n>>31 等于 0，若 n 为负数，n>>31 等于 -1
    若 n 为正数 n^0=n, 数不变，若 n 为负数有 n^(-1)
    需要计算 n 和 -1 的补码，然后进行异或运算，
    结果 n 变号并且为 n 的绝对值减 1，再减去 -1 就是绝对值
    """

取两个数的最大/最小值¶

在某些机器上，效率比 a > b ? a : b 高。

// C++ Version
// 如果 a>=b,(a-b)>>31 为 0，否则为 -1
int max(int a, int b) { return b & ((a - b) >> 31) | a & (~(a - b) >> 31); }
int min(int a, int b) { return a & ((a - b) >> 31) | b & (~(a - b) >> 31); }

# Python Version
# 如果 a>=b,(a-b)>>31 为 0，否则为 -1
def max(a, b):
    return b & ((a - b) >> 31) | a & (~(a - b) >> 31)
def min(a, b):
    return a & ((a - b) >> 31) | b & (~(a - b) >> 31)

判断两非零数符号是否相同¶

// C++ Version
bool isSameSign(int x, int y) {  // 有 0 的情况例外
  return (x ^ y) >= 0;
}

# Python Version
# 有 0 的情况例外
def isSameSign(x, y):
    return (x ^ y) >= 0

交换两个数¶

该方法具有局限性

这种方式只能用来交换两个整数，使用范围有限。

对于一般情况下的交换操作，推荐直接调用 algorithm 库中的 std::swap 函数。

1	void swap(int &a, int &b) { a ^= b ^= a ^= b; }

快速幂

迭代实现

实现方法是非递归式的。它在循环的过程中将二进制位为 1 时对应的幂累乘到答案中。尽管两者的理论复杂度是相同的，但第二种在实践过程中的速度是比第一种更快的，因为递归会花费一定的开销。

a的b次方

b要更新，a要更新，结果要更新

// C++ Version
long long binpow(long long a, long long b) {
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a;
    a = a * a;
    b >>= 1;
  }
  return res;
}

# Python Version
def binpow(a, b):
    res = 1
    while b > 0:
        if (b & 1):
            res = res * a
        a = a * a
        b >>= 1
    return res

应用

模意义下取幂¶

问题描述

计算x^n mod m

这是一个非常常见的应用，例如它可以用于计算模意义下的乘法逆元。

既然我们知道取模的运算不会干涉乘法运算，因此我们只需要在计算的过程中取模即可。

// C++ Version
long long binpow(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}

# Python Version
def binpow(a, b, m):
    a = a % m
    res = 1
    while b > 0:
        if (b & 1):
            res = res * a % m
        a = a * a % m
        b >>= 1
    return res

素数

素数判定¶

我们自然地会想到，如何用计算机来判断一个数是不是素数呢？

暴力做法¶

自然可以枚举从小到大的每个数看是否能整除

// C++ Version   版本一
bool isPrime(a) {
  if (a < 2) return 0;
  for (int i = 2; i < a; ++i)
    if (a % i == 0) return 0;
  return 1;
}

# Python Version
def isPrime(a):
    if a < 2:
        return False
    for i in range(2, a):
        if a % i == 0:
            return False
    return True

// C++ Version
bool isPrime(a) {
  if (a < 2) return 0;
  for (int i = 2; i * i <= a; ++i)
    if (a % i == 0) return 0;
  return 1;
}

# Python Version
def isPrime(a):
    if a < 2:
        return False
    for i in range(2, int(sqrt(a)) + 1):
        if a % i == 0:
            return False
    return True

素性测试¶

素性测试(Primality test）是一类在 不对给定数字进行素数分解（prime factorization）的情况下，测试其是否为素数的算法。

素性测试有两种：

确定性测试：绝对确定一个数是否为素数。常见示例包括 Lucas-Lehmer 测试和椭圆曲线素性证明。
概率性测试：通常比确定性测试快很多，但有可能（尽管概率很小）错误地将合数识别为质数（尽管反之则不会）。因此，通过概率素性测试的数字被称为 可能素数，直到它们的素数可以被确定性地证明。而通过测试但实际上是合数的数字则被称为 伪素数。有许多特定类型的伪素数，最常见的是费马伪素数，它们是满足费马小定理的合数。概率性测试的常见示例包括 Miller–Rabin 测试。

Miller-Rabin 素性测试¶

Miller-Rabin 素性测试（Miller–Rabin primality test）是进阶的素数判定方法。它是由 Miller 和 Rabin 二人根据费马小定理的逆定理（费马测试）优化得到的。因为和许多类似算法一样，它是使用伪素数的概率性测试，我们必须使用慢得多的确定性算法来保证素性。然而，实际上没有已知的数字通过了高级概率性测试（例如 Rabin-Miller）但实际上却是复合的。因此我们可以放心使用。

// C++ Version
bool millerRabin(int n) {
  if (n < 3 || n % 2 == 0) return n == 2;
  int a = n - 1, b = 0;
  while (a % 2 == 0) a /= 2, ++b;
  // test_time 为测试次数,建议设为不小于 8
  // 的整数以保证正确率,但也不宜过大,否则会影响效率
  for (int i = 1, j; i <= test_time; ++i) {
    int x = rand() % (n - 2) + 2, v = quickPow(x, a, n);
    if (v == 1) continue;
    for (j = 0; j < b; ++j) {
      if (v == n - 1) break;
      v = (long long)v * v % n;
    }
    if (j >= b) return 0;
  }
  return 1;
}

# Python Version
def millerRabin(n):
    if n < 3 or n % 2 == 0:
        return n == 2
    a, b = n - 1, 0
    while a % 2 == 0:
        a = a // 2
        b = b + 1
    # test_time 为测试次数,建议设为不小于 8
    # 的整数以保证正确率,但也不宜过大,否则会影响效率
    for i in range(1, test_time + 1):
        x = random.randint(0, 32767) % (n - 2) + 2
        v = quickPow(x, a, n)
        if v == 1:
            continue
        j = 0
        while j < b:
            if v == n - 1:
                break
            v = v * v % n
            j = j + 1
        if j >= b:
            return False
    return True

反素数¶

如果某个正整数 n 满足如下条件，则称为是 反素数：任何小于 n 的正数的约数个数都小于 n 的约数个数

注：注意区分 emirp，它是用来表示从后向前写读是素数的数。

简介¶

其实顾名思义，素数就是因子只有两个的数，那么反素数，就是因子最多的数（并且因子个数相同的时候值最小），所以反素数是相对于一个集合来说的。

我所理解的反素数定义就是，在一个集合中，因素最多并且值最小的数，就是反素数。

分解质因数

因为看不懂，所以我们先去补分解质因数吧！，具体参照的这篇

分解质因数 - 知乎 (zhihu.com)

今天带给大家的题目是：180的约数有多少个？

首先，请允许我普及一下约数的概念。
约数：如果一个自然数A能被自然数B整除，那么称B是A的约数。
知道了约数的概念后，题目就可以重新表述为：180可以被多少个自然数整除？

我现在开始数：有1，2，3，4，5，6，9，10，12，……
停停停！！！
妈呀，好像很多的样子嘛，得一直数到180吗？那也太麻烦了吧。
怎么办，怎么办？？？

化繁为简！
化繁为简是一种非常重要的数学方法，比如在这儿，我们可以把题目改为：
18的约数有多少个？
这样，题目是不是就变得简单多了。
然后通过对这个简单题目的研究，去挖掘其中的一般性结论，最后再推广到数180。
这样不就完美了，哈哈~

好的，说干就干，18的约数有：
1，2，3，6，9，18.
共6个约数，这会有什么结论呢？
老实说，我也看不出！

不过，对于数学老师来说，聊到约数一般都会联系“分解质因数”。
那啥叫“分解质因数”呢？
我再普及一下：把合数表示为质因数乘积的形式叫做“分解质因数”。
那啥又叫“质数”呢？
只能被1和本身这两个不同的自然数整数的自然数叫质数，例如：2，3，5，7，11，……

现在，我们将18进行分解，具体如下：

能从上述式子中找到约数的个数6吗？

我相信你肯定会问我：是质因数2 × 3 = 6，对吗？
哈哈，刚好凑巧罢了，事实上并不对。
那会是什么呢？？？

细心的你肯定是注意到了，
我在质因数2和3的右上角分别标上了它们各自的次数1和2。
这会儿你肯定要笑话我了，
质因数2 × 3 = 6不去相信，次数1和2又怎么能变成6呢？

事实上的结论是：（1 + 1）×（2 + 1）= 6个。
即某一自然数的约数个数是它各质因数的次数分别加1相乘的积！！！

那么，根据上述结论，
我们将180进行分解，具体如下：

则180的约数有：（2 + 1）×（2 + 1）×（1 + 1）= 18个。

到这里，你也许还会想，不是真的吧。
那么，我将180的约数逐一枚举出来，请大家自行检验：
1，2，3，4，5，6，9，10，12，15，18，20，30，36，45，60，90，180.
共18个。

求解反素数

那么，如何来求解反素数呢？

DFS

既然这道题要用到DFS，那么我们去练一道DFS板子题再来吧QW，先继续往下学习

无题

位运算